Lineární vyhledávání: Python, C++ Příklad

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 hledá minimální výšku z daného seznamu výšek nebo hledá nejvyšší hodnotu ze seznamu nebo pole čísel. Mezi několik populárních vyhledávacích algoritmů patří „lineární vyhledávání“, „binární vyhledávání“, „skokové vyhledávání“, „Fibonacciho vyhledávání“ atd.

Co je lineární vyhledávání?

Lineární vyhledávání je jeden 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ým seznamem a kontroluje, zda je nějaký konkrétní prvek shodný s hledaným prvkem. Nazývá se 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 se v poli nenachází.
• 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, že máme pole obsahující celá čísla. Úkolem je najít v tomto poli dané číslo.

• 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) Inicializujte 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 se položka nachází na indexu č. i). Přejděte ke kroku 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.

Nepravý Code pro algoritmus sekvenčního vyhledávání

Následující pseudokód zachycuje logiku výše popsaného lineárního vyhledávání. Prochází pole od prvního indexu a vrací pozici v případě shody, jinak vrací -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 Příklad lineárního vyhledávání

Zde je kompletní C++ program, který implementuje sekvenční vyhledávání a vypíše index hledané hodnoty.

#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;
    }
}

Výstup:

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

Python Code Příklad lineárního vyhledávání

Stejná logika v Python používá jednu smyčku přes indexy seznamu a vrací pozici odpovídajícího prvku.

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 potřebného k provedení určité úlohy. V algoritmu lineárního vyhledávání je úkolem najít klíč k vyhledávání z prvků 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“. Hledaný prvek můžeme najít v rozmezí indexů 0 až n-1. V nejhorším případě se algoritmus pokusí najít všechny prvky z pole odpovídající hledanému prvku.

V takovém případě bude nejhorší případ složitosti O(n). Zde „O“ – velké O – 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 pole. V tomto scénáři lineární vyhledávací algoritmus neprohledá 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 v lineární vyhledávací funkci nemusíme ukládat ani používat žádnou dočasnou proměnnou.

Jak zlepšit lineární vyhledávací algoritmus

Vyhledávání lze provést několikrát během životního cyklu programu. Je také možné, že spouštíme lineární vyhledávací algoritmus a hledáme libovolný konkrétní klíč několikrát. 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ě prohodíme hledaný prvek s jeho předchozím prvkem v poli. Řekněme například, že máte pole podobné tomuto:

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) Prohoďte data[5] a data[4]. Datové pole pak bude vypadat takto:

Data[] = {1,5,9,8,4,7,3,11}

Pokud si všimnete, čím častěji se klíč prohledává, tím více se snižuje index. Tím se snižuje počet porovnání.

Přesuňte se dopředu:

V této metodě prohodíme hledaný prvek na 0. index. Protože pokud se prohledá znovu, najdeme ho za O(1) čas.

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 pouze s několika prvky v seznamu je snazší 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.

Nejčastější dotazy