Lineární vyhledávání: Python, C++ Příklad
Sarah Chen
Co je vyhledávací algoritmus?
Vyhledávací algoritmus je navržen tak, aby našel prvek nebo objekt z kolekce prvků nebo objektů s danou datovou strukturou. Například vyhledejte minimální výšku v daném seznamu výšek nebo vyhledejte nejvyšší značku ze seznamu nebo pole čísel. Několik populárních vyhledávacích algoritmů zahrnuje „Linear Search“, „Binary Search“, „Jump Search“, „Fibonacci Search“ atd.
Co je lineární vyhledávání?
Lineární vyhledávání je jedním z nejjednodušších vyhledávacích algoritmů. Z daného seznamu nebo pole hledá daný prvek jeden po druhém. Lineární vyhledávání iteruje celý seznam a kontroluje, zda se některý konkrétní prvek rovná prvku vyhledávání. Říká se tomu také sekvenční vyhledávání.
Co dělá funkce lineárního vyhledávání?
Pole celých čísel je uvedeno jako „Numbers,“ a proměnná „item“ obsahuje celé číslo, které se má hledat.
Nyní může algoritmus lineárního vyhledávání poskytnout následující výstup:
- "-1"; to znamená, že daný prvek není v poli nalezen
- Libovolné číslo mezi 0 až n-1; znamená, že vyhledávací prvek je nalezen a vrací index prvku v poli. Zde „n“ představuje velikost pole.
Jak funguje lineární vyhledávání?
Řekněme pole obsahující celá čísla. Úkolem je najít dané číslo v poli.
- Pokud se číslo nachází v poli, musíme vrátit index tohoto čísla.
- Pokud se dané číslo nenajde, vrátí -1.
Ve vývojovém diagramu je „Data“ celočíselné pole, „N“ je velikost pole a „položka“ je číslo, které chceme v poli hledat.
Vývojový diagram pro lineární vyhledávací algoritmus:
Zde jsou kroky vývojového diagramu:
Krok 1) Přečtěte si hledanou položku „položka“.
Krok 2) Iniciujte i=0 a index=-1
Krok 3) Kdybych
Krok 4) Pokud se Data[i] rovná „položke“, přejděte ke kroku 5. Jinak přejděte ke kroku 6.
Krok 5) Index = i (Protože položka se nachází na indexu č. i). Přejděte na krok 8.
Krok 6) i = i +1.
Krok 7) Přejděte na krok 3.
Krok 8) Přestaň.
Pro jednoduchost uvádíme příklad s polem celých čísel. Lineární vyhledávání je také použitelné v řetězci, poli objektů nebo struktuře.
Pseudokód pro algoritmus sekvenčního vyhledávání
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++ Příklad kódu Lineární vyhledávání
#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;
}
}
Výstup:
Enter a number to search: -10 -10 is found at index 14
Python Příklad kódu Lineární vyhledávání
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))
Výstup:
Enter a number to search: -10 -10 is found at index 14
Analýza složitosti lineárního vyhledávacího algoritmu
Časová složitost obecně znamená množství času CPU k provedení určitého úkolu. V lineárním vyhledávacím algoritmu je úkolem najít vyhledávací klíč z prvku pole.
Existují tři typy časové složitosti:
- Scénář nejhoršího případu
- Nejlepší případový scénář
- Průměrný případový scénář
Časová složitost lineárního vyhledávání ve scénáři nejhoršího případu:
Řekněme, že potřebujeme provést lineární vyhledávání v poli o velikosti „n“. Hledanou položku najdeme mezi indexem 0 až n-1. V nejhorším případě se algoritmus pokusí porovnat všechny prvky z pole s vyhledávacím prvkem.
V takovém případě bude složitost nejhoršího případu O(n). Zápis „O“-velké O zde znamená funkci složitosti.
Časová složitost lineárního vyhledávání v nejlepším scénáři:
Řekněme, že hledáme prvek, který se nachází na první pozici v poli. V tomto scénáři lineární vyhledávací algoritmus nebude hledat všech n prvků v poli. Složitost tedy bude O(1). To znamená konstantní čas.
Časová složitost lineárního vyhledávání v průměrném scénáři:
Když je prvek nalezen na středním indexu pole, pak lze říci, že průměrná složitost případu pro lineární vyhledávání je O(N), kde N znamená délku pole.
Prostorová složitost lineárního vyhledávacího algoritmu
Prostorová složitost pro lineární vyhledávání je vždy O(N), protože ve funkci lineárního vyhledávání nepotřebujeme ukládat ani používat žádný druh dočasné proměnné.
Jak zlepšit lineární vyhledávací algoritmus
Vyhledávání lze provádět několikrát během životního cyklu programu. Je také možné, že spouštíme lineární vyhledávací algoritmus a několikrát hledáme jakýkoli konkrétní klíč. Můžeme použít „Binární vyhledávací algoritmus” pokud je pole seřazené pole.
Předpokládejme, že pole se skládá z 10 tisíc čísel a cílový prvek se nachází na 5000. indexu. Algoritmus se tedy pokusí porovnat 5000 prvků. Nyní jsou srovnání úlohy náročné na CPU. Pro optimalizaci lineárního vyhledávacího algoritmu máme dvě možnosti.
- Transpozice
- Přesuňte se dopředu
Transpozice:
V této metodě zaměníme vyhledávací prvek s jeho předchozím prvkem v poli. Řekněme například, že máte pole podobné následujícímu:
Data[] = {1,5,9,8,7,3,4,11}
Nyní chceme hledat 4. Kroky transpozice:
Krok 1) „4“ se nachází u indexu 6. Bylo potřeba šest srovnání.
Krok 2) Vyměňte data[6] a data[5]. Poté bude datové pole vypadat takto:
Data[] = {1,5,9,8,7,4,3,11}
Krok 3) Hledejte znovu 4. Nalezeno na indexu 5. Tentokrát to vyžadovalo pět srovnání.
Krok 4) Vyměňte data [5] a data[4]. Potom bude datové pole vypadat takto:
Data [] = {1,5,9,8,4,7,3,11}
Nyní, pokud si všimnete, čím častěji je klíč prohledáván, tím více snižuje index. Sníží se tak počet srovnání.
Přesuňte se dopředu:
Při této metodě prohodíme vyhledávací prvek v 0. indexu. Protože pokud je znovu prohledán, můžeme jej najít v čase O(1).
Aplikace lineárního vyhledávacího algoritmu
Zde jsou některé lineární vyhledávací aplikace, které můžeme použít.
- Pro malá pole nebo jen několik prvků v seznamu je jednodušší použít lineární vyhledávání.
- Metodu lineárního vyhledávání lze použít v jednoduchém resp vícerozměrná pole nebo jiné datové struktury.
- Obecně je lineární vyhledávání jednoduché a efektivní pro provádění vyhledávání v „neuspořádaných“ datech. Z daného neuspořádaného seznamu můžeme snadno načíst jednotlivá data.
