Zanim zrozumiemy różnice między wyszukiwaniem liniowym i binarnym, powinniśmy najpierw poznać osobno wyszukiwanie liniowe i wyszukiwanie binarne.
Co to jest wyszukiwanie liniowe?
Wyszukiwanie liniowe jest również znane jako wyszukiwanie sekwencyjne, które po prostu skanuje każdy element na raz. Załóżmy, że chcemy przeszukać element w tablicy lub liście; po prostu obliczamy jego długość i nie skaczemy na żaden element.
Rozważmy prosty przykład.
Załóżmy, że mamy tablicę składającą się z 10 elementów, jak pokazano na poniższym rysunku:
Powyższy rysunek przedstawia tablicę typów znakowych zawierającą 10 wartości. Jeśli chcemy wyszukać „E”, wyszukiwanie rozpoczyna się od 0telement i skanuje każdy element, aż element, tj. „E”, nie zostanie znaleziony. Nie możemy bezpośrednio przeskoczyć od 0telement do 4telement, tj. każdy element jest skanowany jeden po drugim, aż element nie zostanie znaleziony.
Złożoność przeszukiwania liniowego
Podczas wyszukiwania liniowego skanuje każdy element jeden po drugim, aż element nie zostanie znaleziony. Jeśli liczba elementów wzrasta, zwiększa się także liczba elementów do zeskanowania. Można powiedzieć, że czas potrzebny na przeszukanie elementów jest proporcjonalny do liczby elementów . Dlatego najgorszym przypadkiem złożoności jest O(n)
Co to jest wyszukiwanie binarne?
Wyszukiwanie binarne to wyszukiwanie, w którym obliczany jest środkowy element, aby sprawdzić, czy jest on mniejszy, czy większy od elementu, który ma być przeszukiwany. Główną zaletą wyszukiwania binarnego jest to, że nie skanuje każdego elementu na liście. Zamiast skanować każdy element, przeszukuje połowę listy. Zatem wyszukiwanie binarne zajmuje mniej czasu na przeszukanie elementu w porównaniu z wyszukiwaniem liniowym.
Jeden warunek wstępny wyszukiwania binarnego polega na tym, że tablica powinna być w porządku posortowanym, podczas gdy wyszukiwanie liniowe działa zarówno w przypadku tablicy posortowanej, jak i nieposortowanej. Algorytm wyszukiwania binarnego opiera się na technice dziel i zwyciężaj, co oznacza, że będzie dzielić tablicę rekurencyjnie.
W wyszukiwaniu binarnym stosowane są trzy przypadki:
Przypadek 1: dane
Przypadek 2: dane>a[mid], następnie prawo=mid-1
Przypadek 3: data = a[mid] // znaleziono element
W powyższym przypadku „ A ' jest nazwą tablicy, Środek jest indeksem elementu obliczanym rekurencyjnie, dane jest elementem, który ma być przeszukiwany, lewy oznacza lewy element tablicy i Prawidłowy oznacza element występujący po prawej stronie tablicy.
Przyjrzyjmy się działaniu wyszukiwania binarnego na przykładzie.
Załóżmy, że mamy tablicę o rozmiarze 10, która jest indeksowana od 0 do 9, jak pokazano na poniższym rysunku:
Chcemy wyszukać 70 elementów z powyższej tablicy.
Krok 1: Najpierw obliczamy środkowy element tablicy. Rozważamy dwie zmienne, tj. lewą i prawą stronę. Początkowo lewy = 0 i prawy = 9, jak pokazano na poniższym rysunku:
Wartość środkowego elementu można obliczyć jako:
Zatem mid = 4 i a[mid] = 50. Szukanym elementem jest 70, zatem a[mid] nie jest równe danym. Przypadek 2 jest spełniony, czyli dane>a[mid].
Krok 2: Ponieważ dane>a[mid], wartość left jest zwiększana o mid+1, tj. left=mid+1. Wartość mid wynosi 4, więc wartość left wynosi 5. Teraz mamy podtablicę, jak pokazano na poniższym rysunku:
Teraz ponownie wartość średnią oblicza się za pomocą powyższego wzoru, a wartość środka wynosi 7. Teraz środek można przedstawić jako:
Na powyższym rysunku możemy zaobserwować, że a[mid]>data, więc ponownie wartość mid zostanie obliczona w następnym kroku.
Krok 3: W przypadku danych [mid]> wartość prawa jest zmniejszana o połowę. Wartość mid wynosi 7, więc wartość Right wynosi 6. Tablicę można przedstawić jako:
Wartość mid zostanie obliczona ponownie. Wartości lewej i prawej strony wynoszą odpowiednio 5 i 6. Dlatego wartość mid wynosi 5. Teraz środek można przedstawić w tablicy, jak pokazano poniżej:
Na powyższym rysunku możemy zaobserwować, że [mid]
Krok 4: jako [w środku] Teraz wartość mid jest obliczana ponownie, korzystając ze wzoru, który już omówiliśmy. Wartości lewej i prawej strony wynoszą odpowiednio 6 i 6, więc wartość środka wynosi 6, jak pokazano na poniższym rysunku: Na powyższym rysunku możemy zaobserwować, że a[mid]=data. Dlatego wyszukiwanie zostało zakończone i element został pomyślnie znaleziony. Poniżej przedstawiono różnice między wyszukiwaniem liniowym a wyszukiwaniem binarnym: Opis Wyszukiwanie liniowe to wyszukiwanie, które znajduje element na liście, przeszukując go sekwencyjnie, aż element zostanie znaleziony na liście. Z drugiej strony wyszukiwanie binarne to wyszukiwanie, które rekurencyjnie znajduje środkowy element na liście, dopóki środkowy element nie zostanie dopasowany do szukanego elementu. Działanie obu wyszukiwań Wyszukiwanie liniowe rozpoczyna wyszukiwanie od pierwszego elementu i skanuje jeden element na raz, bez przeskakiwania do następnego elementu. Z drugiej strony wyszukiwanie binarne dzieli tablicę na połowę, obliczając środkowy element tablicy. Realizacja Wyszukiwanie liniowe można zaimplementować na dowolnej liniowej strukturze danych, takiej jak wektor, lista pojedynczo połączona, lista podwójnie połączona. Natomiast wyszukiwanie binarne można wdrożyć w tych strukturach danych z przechodzeniem dwukierunkowym, tj. przechodzeniem do przodu i do tyłu. Złożoność Wyszukiwanie liniowe jest łatwe w użyciu lub można powiedzieć, że jest mniej skomplikowane, ponieważ elementy w wyszukiwaniu liniowym można ułożyć w dowolnej kolejności, podczas gdy w wyszukiwaniu binarnym elementy muszą być ułożone w określonej kolejności. Posortowane elementy Elementy wyszukiwania liniowego można ułożyć w kolejności losowej. W przypadku wyszukiwania liniowego nie jest obowiązkowe, aby elementy były ułożone w posortowanej kolejności. Z drugiej strony w wyszukiwaniu binarnym elementy muszą być ułożone w kolejności posortowanej. Można je ułożyć w kolejności rosnącej lub malejącej, w związku z czym algorytm zostanie zmieniony. Ponieważ wyszukiwanie binarne wykorzystuje posortowaną tablicę, konieczne jest wstawienie elementu w odpowiednim miejscu. Natomiast wyszukiwanie liniowe nie wymaga posortowanej tablicy, dzięki czemu nowy element można łatwo wstawić na końcu tablicy. Zbliżać się Wyszukiwanie liniowe wykorzystuje podejście iteracyjne w celu znalezienia elementu, dlatego jest również znane jako podejście sekwencyjne. Natomiast wyszukiwanie binarne oblicza środkowy element tablicy, dlatego stosuje metodę dziel i zwyciężaj. Zbiór danych Wyszukiwanie liniowe nie jest odpowiednie dla dużych zbiorów danych. Jeśli chcemy przeszukać element będący ostatnim elementem tablicy, przeszukiwanie liniowe rozpocznie się od pierwszego elementu i będzie trwało aż do ostatniego elementu, więc czas potrzebny na przeszukanie elementu będzie duży. Z drugiej strony wyszukiwanie binarne jest odpowiednie w przypadku dużego zbioru danych, ponieważ zajmuje mniej czasu. Prędkość Jeśli zbiór danych w przypadku wyszukiwania liniowego jest duży, koszt obliczeniowy będzie wysoki, a prędkość będzie niska. Jeśli zbiór danych w wyszukiwaniu binarnym jest duży, koszt obliczeniowy będzie mniejszy w porównaniu z wyszukiwaniem liniowym, a prędkość będzie duża. Wymiary Wyszukiwanie liniowe można zastosować zarówno w tablicy jednowymiarowej, jak i wielowymiarowej, natomiast wyszukiwanie binarne można zastosować tylko w tablicy jednowymiarowej. Efektywność Wyszukiwanie liniowe jest mniej efektywne, gdy uwzględnimy duże zbiory danych. W przypadku dużych zbiorów danych przeszukiwanie binarne jest bardziej efektywne niż przeszukiwanie liniowe. Przyjrzyjmy się różnicom w formie tabelarycznej. 
Różnice między wyszukiwaniem liniowym a wyszukiwaniem binarnym
pyspark sql
Podstawa porównania Wyszukiwanie liniowe Wyszukiwanie binarne Definicja Wyszukiwanie liniowe rozpoczyna wyszukiwanie od pierwszego elementu i porównuje każdy element z szukanym elementem, aż element nie zostanie znaleziony. Znajduje pozycję szukanego elementu, znajdując środkowy element tablicy. Posortowane dane W wyszukiwaniu liniowym elementy nie muszą być ułożone w kolejności posortowanej. Warunkiem wyszukiwania binarnego jest uporządkowanie elementów. Realizacja Wyszukiwanie liniowe można wdrożyć na dowolnej liniowej strukturze danych, takiej jak tablica, lista połączona itp. Implementacja wyszukiwania binarnego jest ograniczona, ponieważ można je wdrożyć tylko w tych strukturach danych, które umożliwiają przechodzenie dwukierunkowe. Zbliżać się Opiera się na podejściu sekwencyjnym. Opiera się na podejściu „dziel i zwyciężaj”. Rozmiar Jest to preferowane w przypadku małych zbiorów danych. Jest to preferowane w przypadku dużych zbiorów danych. Efektywność Jest ona mniej efektywna w przypadku dużych zbiorów danych. Jest to bardziej efektywne w przypadku dużych zbiorów danych. Najgorszy scenariusz W przypadku wyszukiwania liniowego najgorszym scenariuszem znalezienia elementu jest O(n). W wyszukiwaniu binarnym najgorszy scenariusz znalezienia elementu to O(log2N). Najlepszy scenariusz W przypadku wyszukiwania liniowego najlepszym scenariuszem znalezienia pierwszego elementu na liście jest O(1). W wyszukiwaniu binarnym najlepszym scenariuszem znalezienia pierwszego elementu na liście jest O(1). Tablica wymiarowa Można go zaimplementować zarówno na tablicy jednowymiarowej, jak i wielowymiarowej. Można go zaimplementować tylko na tablicy wielowymiarowej.