Główna różnica między wyszukiwaniem liniowym a wyszukiwaniem binarnym polega na tym, że wyszukiwanie binarne zajmuje mniej czasu na wyszukanie elementu z posortowanej listy elementów. Wynika z tego, że skuteczność metody wyszukiwania binarnego jest większa niż wyszukiwanie liniowe.
Kolejną różnicą między nimi jest to, że istnieje warunek wstępny do wyszukiwania binarnego, tzn. Elementy muszą być posortowane, podczas gdy w wyszukiwaniu liniowym nie ma takiego warunku wstępnego. Chociaż obie metody wyszukiwania wykorzystują różne techniki, które omówiono poniżej.
Wykres porównania
| Podstawa do porównania | Wyszukiwanie liniowe | Wyszukiwanie binarne |
|---|---|---|
| Złożoność czasu | NA) | O (log 2 N) |
| Najlepszy czas na wykonanie | Pierwszy element O (1) | Element środkowy O (1) |
| Wymaganie wstępne dla tablicy | Nie wymagane | Tablica musi być uporządkowana w kolejności |
| Najgorszy przypadek dla liczby N elementów | N porównań są wymagane | Może kończyć się tylko po porównaniu log 2 N |
| Może być wdrożony na | Lista Array i Linked | Nie można bezpośrednio zaimplementować na liście połączonej |
| Wstaw operację | Łatwe wstawianie na końcu listy | Wymagaj przetwarzania, aby wstawić w odpowiednim miejscu, aby zachować posortowaną listę. |
| Typ algorytmu | Z natury iteracyjny | Dziel i rządź w naturze |
| Przydatność | Łatwy w użyciu i nie wymaga żadnych zamówionych elementów. | W każdym razie podstępny algorytm i elementy powinny być zorganizowane w kolejności. |
| Linie kodu | Mniej | Więcej |
Definicja wyszukiwania liniowego
W wyszukiwaniu liniowym każdy element tablicy jest pobierany jeden po drugim w logicznej kolejności i sprawdzany, czy jest pożądany, czy nie. Wyszukiwanie zakończy się niepowodzeniem, jeśli wszystkie elementy zostaną udostępnione, a żądany element nie zostanie znaleziony. W najgorszym przypadku liczba przeciętnego przypadku może wymagać skanowania połowy rozmiaru tablicy (n / 2).
Dlatego wyszukiwanie liniowe można zdefiniować jako technikę, która sekwencyjnie przechodzi przez macierz w celu zlokalizowania danego elementu. Przedstawiony poniżej program ilustruje przeszukiwanie elementu tablicy za pomocą wyszukiwania.
Efektywność wyszukiwania liniowego
Zużycie czasu lub liczba porównań dokonanych podczas wyszukiwania rekordu w tabeli wyszukiwania określa efektywność tej techniki. Jeśli pożądany rekord znajduje się na pierwszej pozycji w tabeli wyszukiwania, wykonywane jest tylko jedno porównanie. Gdy pożądany rekord jest ostatnim, należy dokonać porównania. Jeśli rekord ma znajdować się gdzieś w tabeli wyszukiwania, średnia liczba porównań będzie wynosić (n + 1/2). Najgorszy przypadek efektywności tej techniki to O (n) oznacza kolejność wykonania.
C Program do wyszukiwania elementu za pomocą techniki wyszukiwania liniowego.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nWprowadź numer elementu:"); scanf ("% d", & n); printf ("Wprowadź liczby: \ n"); dla (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nWprowadź szukany numer:"); scanf ("% d", i element); dla (i = 0; i = 0) {printf ("\ n% d znajduje się w pozycji% d:", element, loc + 1); } else {printf ("\ n Element nie istnieje"); } getch (); } Definicja wyszukiwania binarnego
Wyszukiwanie binarne jest niezwykle wydajnym algorytmem. Ta technika wyszukiwania zajmuje mniej czasu podczas wyszukiwania danego elementu przy minimalnych możliwych porównaniach. Aby wykonać wyszukiwanie binarne, najpierw musimy posortować elementy tablicy.
Logika stojąca za tą techniką jest podana poniżej:
- Najpierw znajdź środkowy element tablicy.
- Środkowy element tablicy jest porównywany z szukanym elementem.
Mogą powstać trzy przypadki:
- Jeśli element jest wymaganym elementem, wyszukiwanie zakończy się pomyślnie.
- Gdy element jest mniejszy niż żądany element, wyszukaj tylko pierwszą połowę tablicy.
- Jeśli jest większy niż żądany element, wyszukaj w drugiej połowie tablicy.
Powtarzaj te same kroki, aż element zostanie znaleziony lub wyczerpany w obszarze wyszukiwania. W tym algorytmie za każdym razem zmniejsza się obszar wyszukiwania. Dlatego liczba porównań wynosi co najwyżej log (N + 1). W rezultacie jest to skuteczny algorytm w porównaniu do wyszukiwania liniowego, ale tablica musi zostać posortowana przed wykonaniem przeszukiwania binarnego.
C Program do znalezienia elementu z techniką wyszukiwania binarnego.
#include void main () {int i, beg, end, middle, n, search, array [100]; printf ("Wprowadź numer elementu \ n"); scanf ("% d", & n); printf ("Wprowadź% d liczb \ n", n); dla (i = 0; i <n; i ++) scanf ("% d", i tablica [i]); printf ("Wprowadź szukany numer \ n"); scanf ("% d", wyszukiwanie); beg = 0; end = n - 1; środek = (początek + koniec) / 2; while (beg <= end) {if (array [middle] end) printf ("Wyszukiwanie zakończone niepowodzeniem!% d nie występuje na liście. \ n", szukaj); getch (); } Kluczowe różnice między wyszukiwaniem liniowym a wyszukiwaniem binarnym
- Wyszukiwanie liniowe ma charakter iteracyjny i wykorzystuje podejście sekwencyjne. Z drugiej strony wyszukiwarka binarna implementuje podejście dziel i podbijaj.
- Złożoność czasowa wyszukiwania liniowego to O (N), natomiast wyszukiwanie binarne ma O (log 2 N).
- Najlepszy przypadek w wyszukiwaniu liniowym dotyczy pierwszego elementu, tj. O (1). W przeciwieństwie do tego, w wyszukiwaniu binarnym jest to element środkowy, tj. O (1).
- W wyszukiwaniu liniowym najgorszym przypadkiem przeszukiwania elementu jest liczba porównań N. Dla porównania jest to log 2 N liczby porównań dla wyszukiwania binarnego.
- Wyszukiwanie liniowe może być realizowane zarówno w postaci tablicy, jak i listy połączonej, podczas gdy wyszukiwanie binarne nie może być zaimplementowane bezpośrednio na liście połączonej.
- Jak wiemy, wyszukiwanie binarne wymaga uporządkowanej tablicy, która jest powodem Wymaga przetwarzania, aby wstawić w odpowiednim miejscu, aby utrzymać posortowaną listę. W przeciwieństwie do tego wyszukiwanie liniowe nie wymaga posortowanych elementów, więc elementy można łatwo wstawiać na końcu listy.
- Wyszukiwanie liniowe jest łatwe w użyciu i nie wymaga żadnych uporządkowanych elementów. Z drugiej strony algorytm wyszukiwania binarnego jest skomplikowany, a elementy muszą być uporządkowane w kolejności.
Wniosek
Zarówno algorytmy wyszukiwania liniowego, jak i binarnego mogą być przydatne w zależności od aplikacji. Kiedy tablica jest strukturą danych, a elementy są ułożone w porządku posortowanym, wówczas wyszukiwanie binarne jest preferowane do szybkiego wyszukiwania. Jeśli połączona lista jest strukturą danych niezależnie od tego, w jaki sposób są rozmieszczone elementy, przeszukiwanie liniowe zostaje przyjęte z powodu niedostępności bezpośredniej implementacji algorytmu binarnego wyszukiwania.
Typowy algorytm wyszukiwania binarnego nie może być zastosowany do listy połączonej, ponieważ lista połączona ma charakter dynamiczny i nie wiadomo, gdzie element środkowy jest rzeczywiście przypisany. Stąd istnieje wymóg zaprojektowania odmiany algorytmu binarnego wyszukiwania, który może działać na liście połączonej, ponieważ wyszukiwanie binarne jest szybsze w wykonaniu niż wyszukiwanie liniowe.
![Media społecznościowe - 5050 lat w 150 sekund [wideo]](https://gadget-info.com/img/social-media/580/5050-years-150-seconds.jpg)
