Wprowadzenie do algorytmów wyszukiwania

nie ma nawet jednego dnia, kiedy nie musimy szukać czegoś w naszym codziennym życiu, kluczy samochodowych, książek, długopisu, Ładowarki mobilnej i czego nie. Tak samo jest z życiem komputera, jest w nim tak dużo danych, że gdy użytkownik prosi o dane, komputer musi przeszukać pamięć, aby wyszukać Dane i udostępnić je użytkownikowi. Komputer ma własne techniki szybkiego przeszukiwania pamięci, o których możesz dowiedzieć się więcej w naszej serii samouczków dotyczących systemu operacyjnego.

co jeśli musisz napisać program do wyszukiwania danej liczby w tablicy? Jak to zrobisz?

Cóż, aby wyszukać element w danej tablicy, dostępne są dwa popularne algorytmy:

1. Wyszukiwanie liniowe
2. Wyszukiwanie binarne

Wyszukiwanie liniowe

Wyszukiwanie liniowe jest bardzo prostym algorytmem wyszukiwania. W wyszukiwaniu liniowym wyszukujemy element lub wartość w danej tablicy przechodząc ją od początku aż do znalezienia żądanego elementu lub wartości.

porównuje wyszukiwany element ze wszystkimi elementami obecnymi w tablicy, a gdy element zostanie pomyślnie dopasowany, zwraca indeks elementu w tablicy, w przeciwnym razie zwraca -1.

Wyszukiwanie liniowe jest stosowane na listach nieposortowanych lub nieuporządkowanych, gdy na liście jest mniej elementów.

cechy liniowego algorytmu wyszukiwania

1. służy do nieposortowanych i nieuporządkowanych małych list elementów.
2. ma złożoność czasową O(n), co oznacza, że czas jest liniowo zależny od liczby elementów, co nie jest złe, ale też nie tak dobre.
3. ma bardzo prostą implementację.

zaimplementujemy algorytm wyszukiwania liniowego w następnym tutorialu.

Wyszukiwanie binarne

Wyszukiwanie binarne jest używane z posortowaną tablicą lub listą. W wyszukiwaniu binarnym wykonujemy następujące kroki:

1. zaczynamy od porównania szukanego elementu z elementem w środku listy/tablicy.
2. jeśli otrzymamy dopasowanie, zwracamy indeks środkowego elementu.
3. jeśli nie uzyskamy dopasowania, sprawdzamy, czy poszukiwany element jest mniejszy lub większy niż wartość środkowego elementu.
4. jeśli poszukiwany element / liczba ma większą wartość niż liczba środkowa, to wybieramy elementy po prawej stronie środkowego elementu (ponieważ lista/tablica jest posortowana, stąd po prawej będziemy mieć wszystkie liczby większe niż liczba Środkowa) i zaczynamy od kroku 1.
5. jeśli poszukiwany element / liczba ma mniejszą wartość niż liczba środkowa, to wybieramy elementy po lewej stronie środkowego elementu i zaczynamy od kroku 1.

Wyszukiwanie binarne jest przydatne, gdy w tablicy znajduje się duża liczba elementów i są one posortowane.

tak więc warunkiem koniecznym do działania wyszukiwania binarnego jest posortowanie listy / tablicy.

funkcje wyszukiwania binarnego

1. wspaniale jest przeszukiwać Duże posortowane tablice.
2. ma złożoność czasową O(log N), która jest bardzo dobrą złożonością czasową. Omówimy to szczegółowo w samouczku wyszukiwania binarnego.
3. ma prostą implementację.