Zawartość

• Wykres porównania
• Definicja wyszukiwania liniowego
• Definicja wyszukiwania binarnego
• Wniosek

Wyszukiwanie liniowe i wyszukiwanie binarne to dwie metody stosowane w tablicach badawczy elementy. Wyszukiwanie to proces znajdowania elementu na liście elementów przechowywanych w dowolnej kolejności lub losowo.

Główną różnicą między wyszukiwaniem liniowym a wyszukiwaniem binarnym jest to, że wyszukiwanie binarne zajmuje mniej czasu na wyszukiwanie elementu z posortowanej listy elementów. Można więc wywnioskować, że wydajność metody wyszukiwania binarnego jest większa niż w przypadku wyszukiwania liniowego.

Inna różnica między nimi polega na tym, że wyszukiwanie binarne jest warunkiem wstępnym, tzn. Elementy muszą być posortowane podczas gdy w wyszukiwaniu liniowym nie ma takich wymagań wstępnych. Chociaż obie metody wyszukiwania wykorzystują różne techniki omówione poniżej.

1. Wykres porównania
2. Definicja
3. Kluczowe różnice
4. Wniosek

Wykres porównania

Podstawa do porównania	Wyszukiwanie liniowe	Wyszukiwanie binarne
Złożoność czasu	NA)	O (log 2 N)
Najlepszy czas sprawy	Pierwszy element O (1)	Element środkowy O (1)
Warunek wstępny dla tablicy	Nie wymagane	Tablica musi być posortowana
Najgorszy przypadek dla liczby N elementów	Wymagane jest porównanie N	Można zawrzeć tylko po zalogowaniu2N porównania
Może być wdrożony w dniu	Tablica i lista połączona	Nie można bezpośrednio zaimplementować na połączonej liście
Wstaw operację	Łatwo wstawiany na końcu listy	Wymagaj przetwarzania, aby wstawić w odpowiednim miejscu, aby zachować posortowaną listę.
Rodzaj algorytmu	Iteracyjny z natury	Dziel i rządź w naturze
Przydatność	Łatwy w użyciu i nie wymaga żadnych zamówionych elementów.	W każdym razie skomplikowane algorytmy i elementy powinny być uporządkowane 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 to pożądany element, czy nie. Wyszukiwanie zakończy się niepowodzeniem, jeśli wszystkie elementy zostaną otwarte, a żądany element nie zostanie znaleziony. W najgorszym przypadku liczba przeciętnego przypadku może być potrzebna do zeskanowania połowy rozmiaru tablicy (n / 2).

Dlatego też wyszukiwanie liniowe można zdefiniować jako technikę sekwencyjnego przemierzania tablicy w celu zlokalizowania danego elementu. Program podany poniżej ilustruje wyszukiwanie elementu tablicy za pomocą funkcji wyszukiwania.

Wydajność wyszukiwania liniowego

Zużycie czasu lub liczba porównań dokonanych podczas wyszukiwania rekordu w tabeli wyszukiwania determinuje wydajność techniki. Jeśli żądany rekord znajduje się na pierwszej pozycji tabeli wyszukiwania, wówczas wykonywane jest tylko jedno porównanie. Gdy pożądany zapis jest ostatnim, należy dokonać porównań n. Jeśli rekord ma być prezentowany gdzieś w tabeli wyszukiwania, średnia liczba porównań wyniesie (n + 1/2). Najgorszy przypadek skuteczności tej techniki to O (n) oznacza kolejność wykonywania.

Program C. do wyszukiwania elementu za pomocą techniki wyszukiwania liniowego.

#zawierać #zawierać void main () {int a, n, i, item, loc = -1; clrscr (); f (" nWpisz liczbę elementów:"); scanf („% d”, & n); f („Wprowadź liczby: n”); dla (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nWprowadź szukany numer:"); scanf („% d” i pozycja); dla (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; złamać; }} if (loc> = 0) {f (" n% d znaleziono w pozycji% d:", pozycja, loc + 1); } else {f („ n Element nie istnieje”); } getch (); }

Definicja wyszukiwania binarnego

Wyszukiwanie binarne jest niezwykle wydajnym algorytmem. Ta technika wyszukiwania zużywa mniej czasu na wyszukiwanie danego elementu w minimalnych możliwych porównaniach. Aby przeprowadzić wyszukiwanie binarne, najpierw musimy posortować elementy tablicy.

Logikę tej techniki podano poniżej:

• Najpierw znajdź środkowy element tablicy.
• Środkowy element tablicy jest porównywany z elementem do przeszukania.

Mogą wystąpić trzy przypadki:

1. Jeśli element jest wymaganym elementem, wyszukiwanie zakończy się powodzeniem.
2. Gdy element jest mniejszy niż pożądany element, przeszukaj tylko pierwszą połowę tablicy.
3. Jeśli jest większy niż pożą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ń jest co najwyżej log (N + 1). W rezultacie jest to wydajny algorytm w porównaniu do wyszukiwania liniowego, ale tablica musi zostać posortowana przed wykonaniem wyszukiwania binarnego.

Program C. znaleźć element z techniką wyszukiwania binarnego.

#zawierać void main () {int i, beg, end, middle, n, search, array; f („Wprowadź liczbę elementów n”); scanf („% d”, & n); f („Wprowadź% d liczby n”, n); dla (i = 0; i <n; i ++) scanf ("% d", & array); f („Wprowadź numer do przeszukania n”); scanf („% d” i wyszukiwanie); żebr = 0; end = n - 1; środek = (początek + koniec) / 2; while (beg <= end) {if (tablica <szukaj) beg = środkowy + 1; else if (array == search) {f ("Wyszukiwanie powiodło się. n% d znaleziono w lokalizacji% d. n", wyszukiwanie, środkowy + 1); złamać; } else end = środek - 1; środek = (początek + koniec) / 2; } if (beg> end) f ("Wyszukiwanie nie powiodło się!% d nie jest obecny na liście. n", szukaj); getch (); }

1. Wyszukiwanie liniowe ma charakter iteracyjny i wykorzystuje podejście sekwencyjne. Z drugiej strony, wyszukiwanie binarne implementuje podejście dziel i zwyciężaj.
2. Złożoność czasowa wyszukiwania liniowego wynosi O (N), podczas gdy wyszukiwanie binarne ma O (log₂N).
3. Najlepszy czas obserwacji w wyszukiwaniu liniowym to pierwszy element, tj. O (1). Przeciwnie, w wyszukiwaniu binarnym dotyczy elementu środkowego, tj. O (1).
4. W wyszukiwaniu liniowym najgorszym przypadkiem wyszukiwania elementu jest liczba N porównania. Natomiast jest to log₂Liczba N porównania dla wyszukiwania binarnego.
5. Wyszukiwanie liniowe może być realizowane zarówno w tablicy, jak i na liście połączonej, podczas gdy wyszukiwanie binarne nie może być realizowane bezpośrednio na liście połączonej.
6. Jak wiemy, wyszukiwanie binarne wymaga posortowanej tablicy, która jest przyczyną. Wymaga przetworzenia, aby wstawić w odpowiednim miejscu, aby zachować posortowaną listę. Przeciwnie, wyszukiwanie liniowe nie wymaga posortowanych elementów, więc elementy można łatwo wstawić 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 jednak trudny, a elementy są koniecznie uporządkowane.

Wniosek

W zależności od aplikacji przydatne mogą być zarówno algorytmy wyszukiwania liniowego, jak i binarnego. Gdy tablica jest strukturą danych, a elementy są ułożone w posortowanej kolejności, preferowane jest wyszukiwanie binarne szybkibadawczy. Jeśli połączona lista jest strukturą danych bez względu na to, jak rozmieszczone są elementy, wyszukiwanie liniowe jest przyjmowane z powodu niedostępności bezpośredniej implementacji algorytmu wyszukiwania binarnego.

Typowy algorytm wyszukiwania binarnego nie może być zastosowany do listy połączonej, ponieważ lista połączona ma charakter dynamiczny i nie wiadomo, gdzie faktycznie przypisano środkowy element. Dlatego istnieje potrzeba zaprojektowania wariantu algorytmu wyszukiwania binarnego, który może również działać na liście połączonej, ponieważ wyszukiwanie binarne jest szybsze w wykonywaniu niż wyszukiwanie liniowe.