Лінійний пошук: Python, C++ Приклад

Що таке алгоритм пошуку?

Алгоритм пошуку призначений для пошуку елемента або об’єкта з набору елементів або об’єктів із заданою структурою даних. Наприклад, знайдіть мінімальну висоту в заданому списку висот або знайдіть найвищу позначку в списку чи масиві чисел. Кілька популярних алгоритмів пошуку включають «Лінійний пошук», «Двійковий пошук», «Пошук з переходом», «Пошук за Фібоначчі» тощо.

Що таке лінійний пошук?

Лінійний пошук є одним із найпростіших алгоритмів пошуку. У заданому списку або масиві він шукає заданий елемент один за іншим. Лінійний пошук повторює весь список і перевіряє, чи дорівнює певний елемент пошуковому елементу. Його також називають послідовний пошук.

Що робить функція лінійного пошуку?

Масив цілих чисел задається як “Numbers”, а змінна “item” містить ціле число для пошуку.

Тепер алгоритм лінійного пошуку може забезпечити такі результати:

• «-1»; це означає, що заданий елемент не знайдено в масиві
• Будь-яке число від 0 до n-1; означає, що пошуковий елемент знайдено, і він повертає індекс елемента в масиві. Тут «n» означає розмір масиву.

Як працює лінійний пошук?

Скажімо, масив, що містить цілі числа. Завдання полягає в тому, щоб знайти задане число в масиві.

• Якщо число знаходиться в масиві, нам потрібно повернути індекс цього числа.
• Якщо вказане число не знайдено, воно поверне -1.

На блок-схемі «Дані» — це масив цілих чисел, «N» — це розмір масиву, а «елемент» — це число, яке ми хочемо шукати в масиві.

Блок-схема для алгоритму лінійного пошуку:

Ось кроки блок-схеми:

Крок 1) Прочитайте пошуковий елемент «item».

Крок 2) Ініціювати i=0 та index=-1

Крок 3) Якщо я

Крок 4) Якщо Data[i] дорівнює «item», перейдіть до кроку 5. Інакше перейдіть до кроку 6.

Крок 5) Індекс = i (оскільки елемент знаходиться під індексом i). Перейдіть до кроку 8.

Крок 6) i = i +1.

Крок 7) Перейдіть до кроку 3.

Крок 8) Стоп.

Для простоти наведемо приклад із масивом цілих чисел. Лінійний пошук також можна застосувати в рядку, масиві об’єктів або структурі.

Псевдокод для алгоритму послідовного пошуку

function linearSearch: in →Data[], item
foundAt = -1
for i in (0 to data.length): if data[i] equals item
// item is found in the array
// returning the index
return i
// item not found in the array
// -1 means no item found, as negative index is not valid
return -1

C++ Лінійний пошук прикладу коду

#include < bits / stdc++.h >
    using namespace std;
int linearSearch(int * arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}
int main() {
    int array[] = {
        1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
    };
    int n = sizeof(array) / sizeof(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

вихід:

Enter a number to search: -10
-10 is found at index 14

Python Лінійний пошук прикладу коду

def linearSearch(data, item):
    for i in range(len(data)):
    if data[i] == item:
    return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else :
    print("{} was not found".format(item))

вихід:

Enter a number to search: -10
-10 is found at index 14

Аналіз складності алгоритму лінійного пошуку

Як правило, часова складність означає кількість часу процесора для виконання певного завдання. В алгоритмі лінійного пошуку завдання полягає в пошуку ключа пошуку з елемента масиву.

Три типи часових складностей:

• Найгірший випадок
• Найкращий сценарій
• Сценарій середнього випадку

Часова складність лінійного пошуку в найгіршому сценарії:

Скажімо, нам потрібно виконати лінійний пошук в масиві розміром «n». Ми можемо знайти пошуковий елемент між індексами від 0 до n-1. У найгіршому випадку алгоритм спробує зіставити всі елементи масиву з пошуковим елементом.

У цьому випадку найгіршою складністю буде O(n). Тут “O”-велике позначення O означає функцію складності.

Часова складність лінійного пошуку в найкращому сценарії:

Скажімо, ми шукаємо елемент, який знаходиться на першій позиції в масиві. У цьому сценарії алгоритм лінійного пошуку не шукатиме всі n елементів у масиві. Отже, складність буде O(1). Це означає постійний час.

Час Складність лінійного пошуку в середньому сценарії:

Коли елемент знайдено за середнім індексом масиву, можна сказати, що середня складність випадку для лінійного пошуку становить O(N), де N означає довжину масиву.

Просторова складність алгоритму лінійного пошуку

Складність простору для лінійного пошуку завжди дорівнює O(N), оскільки нам не потрібно зберігати або використовувати будь-яку тимчасову змінну у функції лінійного пошуку.

Як покращити алгоритм лінійного пошуку

Пошук можна виконувати кілька разів протягом життєвого циклу програми. Також можливо, що ми запускаємо алгоритм лінійного пошуку та шукаємо будь-який конкретний ключ кілька разів. Ми можемо використовувати "Алгоритм бінарного пошуку», якщо масив є відсортованим масивом.

Припустимо, що масив складається з 10 тисяч чисел, а цільовий елемент знайдено за 5000-м індексом. Отже, алгоритм спробує порівняти 5000 елементів. Тепер порівняння є важким завданням для ЦП. Для оптимізації алгоритму лінійного пошуку у нас є два варіанти.

• перестановка
• Перейти на передній план

Транспонування:

У цьому методі ми замінимо пошуковий елемент його попереднім елементом у масиві. Наприклад, припустимо, що у вас є такий масив:

Дані[] = {1,5,9,8,7,3,4,11}

Тепер ми хочемо виконати пошук 4. Етапи транспозиції:

Крок 1) «4» знаходиться під індексом 6. Знадобилося шість порівнянь.

Крок 2) Поміняти дані [6] і дані [5]. Тоді масив даних матиме такий вигляд:

Дані[] = {1,5,9,8,7,4,3,11}

Крок 3) Шукайте 4 знову. Знайдено за індексом 5. Цього разу знадобилося п'ять порівнянь.

Крок 4) Поміняти дані [5] і дані [4]. Тоді масив даних матиме такий вигляд:

Дані [] = {1,5,9,8,4,7,3,11}

Тепер, якщо ви помітили, чим частіше виконується пошук ключа, тим більше він зменшує індекс. Таким чином, зменшується кількість порівнянь.

Перейти на передню частину:

У цьому методі ми міняємо пошуковий елемент у 0-му індексі. Тому що, якщо його шукати знову, ми можемо знайти його за час O(1).

Застосування алгоритму лінійного пошуку

Ось деякі програми лінійного пошуку, які ми можемо використовувати.

• Для невеликих масивів або лише кількох елементів у списку простіше використовувати лінійний пошук.
• Лінійний метод пошуку можна використовувати в одиночних або багатовимірні масиви або інші структури даних.
• Як правило, лінійний пошук простий і ефективний для виконання пошуку в «невпорядкованих» даних. Ми можемо легко отримати окремі дані з заданого невпорядкованого списку.