Wprowadzenie do algorytmu wyszukiwania liniowego: wprowadzenie i funkcje [z przykładami]

Co to jest wyszukiwanie?

Wyszukiwanie to proces znajdowania danego elementu na liście elementów. Pomaga w wyszukiwaniu konkretnego rekordu. Jest to zatem technika identyfikacji miejsca danego przedmiotu. Powodzenie procesu wyszukiwania zależy od tego, czy poszukiwany element został zidentyfikowany, czy nie.

Struktura danych umożliwia wyszukiwanie danych dwoma metodami.

1. Wyszukiwanie liniowe lub sekwencyjne
2. Wyszukiwanie binarne

Wyszukiwanie liniowe

Algorytmy wyszukiwania liniowego są rodzajem algorytmu do sekwencyjnego wyszukiwania danych. Algorytm ten znajduje dany element o złożoności O(n). Jest stosowany do kolekcji przedmiotów. Każdy element danych jest przeszukiwany sekwencyjnie i zwracany, jeśli pasuje do szukanego elementu. Jeśli nie zostaną znalezione żadne dopasowania, wyszukiwanie trwa do końca zebranych danych. Jest to w zasadzie technika eksploracji każdego elementu podczas przeglądania listy. Algorytm wyszukiwania można zastosować zarówno do posortowanych, jak i nieposortowanych danych. Praktycznie wyszukiwanie liniowe jest rzadko używane ze względu na szybsze opcje wyszukiwania zapewniane przez inne algorytmy wyszukiwania, takie jak algorytmy wyszukiwania binarnego i tablice haszujące.

Kroki w algorytmie wyszukiwania liniowego

• Odczytanie elementu wyszukiwania przez użytkownika.
• Przeszukiwany element jest skompresowany z pierwszym elementem listy.
• Jeśli elementy pasują, generowany jest zwrot.
• Jeśli elementy nie pasują do siebie, wyszukiwany element jest porównywany z drugim elementem listy.
• Proces jest powtarzany aż do dopasowania elementu.

Cechy algorytmów wyszukiwania liniowego

1. Zwykle stosuje się go do małej listy nieposortowanych lub nieuporządkowanych danych.
2. Czas jest liniowo zależny od liczby elementów, dlatego ma złożoność czasową, jeśli O(n).
3. Implementacja jest bardzo prosta.

Algorytmy wyszukiwania liniowego

Metoda ciągłego zapętlania trwa, dopóki element nie zostanie znaleziony

• algorytm Seqnl_Search(lista, pozycja)
• Pre: lista != ;
• Post: zwróć indeks elementu, jeśli został znaleziony, w przeciwnym razie: 1
• indeks <- fi
• while index < list.Cnt and list[index] != item //cnt: counter zmienna
• indeks <- indeks + 1
• zakończ, gdy
• if index < list.Cnt and list[index] = item
• indeks zwrotu
• koniec jeśli
• powrót: 1
• koniec Seqnl_Search

Przykład wyszukiwania liniowego

Problem: Mając tablicę arr[] składającą się z n elementów, napisz funkcję przeszukującą dany element x w arr[].

Rysunek 1: Przykładowy kod pokazujący implementację algorytmu wyszukiwania liniowego

Źródło

Algorytmy wyszukiwania liniowego mogą być używane w kilku językach programowania.

1. Wyszukiwanie liniowe w Pythonie

Rysunek 2: Przykład kodu przedstawiający algorytm wyszukiwania liniowego w języku Python

Źródło

Dane wyjściowe: Element jest obecny w indeksie 3

2. Wyszukiwanie liniowe w C

Rysunek 3: Przykładowy kod pokazujący algorytm wyszukiwania liniowego w języku C

Źródło

Wyjście : Element jest obecny w indeksie 3

3. Wyszukiwanie liniowe w strukturze danych

Pseudokod dla liniowego problemu wyszukiwania w strukturze danych to

Rysunek 4: Pseudokod dla algorytmu wyszukiwania liniowego

Źródło

Wyszukiwanie binarne

Wyszukiwanie binarne to algorytm do wyszukiwania elementów w tablicy elementów. W porównaniu z algorytmem wyszukiwania liniowego, algorytm wyszukiwania binarnego jest stosowany do posortowanej listy danych.

Algorytm wyszukiwania binarnego obejmuje następujące kroki

• Porównanie szukanego elementu z elementem ze środka listy lub tablicy.
• Jeśli element pasuje do elementu z listy, zwraca indeks elementu środkowego.
• Jeśli nie zostanie zwrócone żadne dopasowanie, sprawdzane jest, czy element jest większy lub mniejszy niż element środkowy.
• W przypadku elementu o większej wartości niż element środkowy wyszukiwanie odbywa się po prawej stronie tablicy.
• Podobnie, jeśli element ma mniejszą wartość niż element środkowy, wyszukiwanie odbywa się po lewej stronie listy.

Dlatego wyszukiwanie binarne najlepiej jest stosować, gdy dane zawierają dużą liczbę elementów prętowych w sposób posortowany. To sprawia, że ​​algorytm wyszukiwania musi sortować listę/tablicę.

Funkcje wyszukiwania binarnego

• Algorytm wyszukiwania binarnego jest przydatny do wyszukiwania dużej liczby elementów w tablicy.
• Algorytm wyszukiwania binarnego ma złożoność czasową O(logn).
• Implementacja algorytmu wyszukiwania binarnego jest prosta.

Algorytm wyszukiwania binarnego

• Algorytm Binary_Search (lista, pozycja)
• Ustaw L na 0 i R na n: 1
• jeśli L > R, to Binary_Search kończy się niepowodzeniem
• w przeciwnym razie
• Ustaw m (pozycja w środkowym elemencie) do podłogi (L + R) / 2
• jeśli Am < T, ustaw L na m + 1 i przejdź do kroku 3
• jeśli Am > T, ustaw R na m: 1 i przejdź do kroku 3
• Teraz jestem = T,
• wyszukiwanie zostało zakończone; powrót (m)

Wniosek

W tym artykule przyjrzeliśmy się, czym jest algorytm wyszukiwania liniowego, a także szczegółowo zbadaliśmy, jak wyszukać określony element z listy za pomocą algorytmu wyszukiwania liniowego. Na koniec zobaczyliśmy również, jak możemy praktycznie zaimplementować algorytm wyszukiwania liniowego przy użyciu Pythona 3 jako języka i uzyskać pożądane wyniki.

Jeśli jesteś zainteresowany Data Science, musisz sprawdzić program PG Executive PG w Data Science IIIT-B i upGrad, który został starannie przygotowany dla pracujących profesjonalistów i oferuje liczne studia przypadków, praktyczne warsztaty, mentoring 1-na-1 i wiele więcej.