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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Крок 3) Якщо я

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

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

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

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

Крок 8) Стоп.

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

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

Наведений нижче псевдокод відображає логіку лінійного пошуку, описаного вище. Він обходить масив, починаючи з першого індексу, і повертає позицію за збігом, інакше повертає -1.

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 a negative index is not valid
    return -1

C++ Code Приклад лінійного пошуку

Ось повний 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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Приклад лінійного пошуку

Та ж логіка в 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» — позначення big 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) Поміняйте місцями data[5] та data[4]. Тоді масив даних виглядатиме так:

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

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

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

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

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

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

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

Поширені запитання