Линейно търсене: Python, C++ Пример

Какво е алгоритъм за търсене?

Алгоритъмът за търсене е предназначен да намери елемент или обект от колекция от елементи или обекти с дадена структура на данните. Например, търсене на минималната височина от даден списък с височини или търсене на най-високата точка от списък или масив от числа. Няколко популярни алгоритми за търсене включват „Линейно търсене“, „Двоично търсене“, „Търсене със скок“, „Търсене по Фибоначи“ и др.

Какво е линейно търсене?

Линейно търсене е един от най-простите алгоритми за търсене. От даден списък или масив, той търси дадения елемент един по един. Линейното търсене итерира през целия списък и проверява дали някой конкретен елемент е равен на търсения елемент. Нарича се още последователно търсене.

Какво прави функцията за линейно търсене?

Масив от цели числа е даден като „Numbers”, а променливата „елемент” съдържа цялото число за търсене.

Сега алгоритъмът за линейно търсене може да предостави следния резултат:

• „-1“; това означава, че даденият елемент не е намерен в масива.
• Всяко число между 0 до n-1; означава, че търсеният елемент е намерен и връща индекса на елемента в масива. Тук "n" представлява размера на масива.

Как работи линейното търсене?

Да кажем, че има масив, съдържащ цели числа. Задачата е да се намери дадено число в масива.

• Ако числото се намира в масива, трябва да върнем индекса на това число.
• Ако даденото число не бъде намерено, то ще върне -1.

В блок-схемата „Данни“ е масивът с цели числа, „N“ е размерът на масива, а „елементът“ е числото, което искаме да търсим в масива.

Блок-схема за алгоритъм за линейно търсене:

Ето стъпките на блок-схемата:

Стъпка 1) Прочетете елемента за търсене, „елемент“.

Стъпка 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) Разменете данни[5] и данни[4]. Тогава масивът от данни ще изглежда така:

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

Сега, ако забележите, колкото по-често се търси даден ключ, толкова повече намалява индексът. По този начин се намалява броят на сравненията.

Преместване отпред:

В този метод разменяме търсения елемент с нулевия индекс. Защото, ако се търси отново, можем да го намерим за O(1) време.

Приложение на алгоритъм за линейно търсене

Ето някои приложения за линейно търсене, които можем да използваме.

• За масиви с малък размер или само няколко елемента в списъка е по-лесно да се използва линейно търсене.
• Методът на линейното търсене може да се използва в единичен или многомерни масиви или други структури от данни.
• Като цяло линейното търсене е просто и ефективно за извършване на търсене в „неподредените“ данни. Можем лесно да извлечем отделни данни от дадения неподреден списък.

Въпроси и Отговори