Линейно търсене: 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) Спри.
За простота предоставяме пример с масив от цели числа. Линейното търсене е приложимо и в низ, масив от обекти или структура.
Псевдо код за алгоритъм за последователно търсене
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) време.
Приложение на алгоритъм за линейно търсене
Ето някои приложения за линейно търсене, които можем да използваме.
- За масиви с малък размер или само няколко елемента в списъка е по-лесно да използвате линейно търсене.
- Методът на линейното търсене може да се използва в единичен или многомерни масиви или други структури от данни.
- Като цяло линейното търсене е просто и ефективно за извършване на търсене в „неподредените“ данни. Можем лесно да извлечем отделни данни от дадения неподреден списък.
