Zalecane, 2024

Wybór Redakcji

Różnica między wyszukiwaniem liniowym a wyszukiwaniem binarnym

Wyszukiwanie liniowe i wyszukiwanie binarne to dwie metody używane w tablicach do wyszukiwania elementów. Wyszukiwanie to proces znajdowania elementu na liście elementów przechowywanych w dowolnej kolejności lub losowo.

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ównaniaWyszukiwanie linioweWyszukiwanie binarne
Złożoność czasuNA)O (log 2 N)
Najlepszy czas na wykonaniePierwszy element O (1)Element środkowy O (1)
Wymaganie wstępne dla tablicyNie wymaganeTablica musi być uporządkowana w kolejności
Najgorszy przypadek dla liczby N elementówN porównań są wymaganeMoże kończyć się tylko po porównaniu log 2 N
Może być wdrożony naLista Array i LinkedNie można bezpośrednio zaimplementować na liście połączonej
Wstaw operacjęŁatwe wstawianie na końcu listyWymagaj przetwarzania, aby wstawić w odpowiednim miejscu, aby zachować posortowaną listę.
Typ algorytmuZ natury iteracyjnyDziel 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 koduMniejWię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:

  1. Jeśli element jest wymaganym elementem, wyszukiwanie zakończy się pomyślnie.
  2. Gdy element jest mniejszy niż żądany element, wyszukaj tylko pierwszą połowę tablicy.
  3. 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

  1. Wyszukiwanie liniowe ma charakter iteracyjny i wykorzystuje podejście sekwencyjne. Z drugiej strony wyszukiwarka binarna implementuje podejście dziel i podbijaj.
  2. Złożoność czasowa wyszukiwania liniowego to O (N), natomiast wyszukiwanie binarne ma O (log 2 N).
  3. 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).
  4. 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.
  5. 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.
  6. 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.
  7. 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.

Top