Wyszukiwanie liniowe a wyszukiwanie binarne: różnica między wyszukiwaniem liniowym a wyszukiwaniem binarnym

Opublikowany: 2021-02-09

Spis treści

Wstęp

Ciągła alokacja pamięci w językach programowania zapewnia elastyczną implementację przechowywania wielu punktów danych. Można to wykorzystać w szczytowym momencie, jeśli chcemy segregować dane i scalać wszystkie podobne dane w ciągłą strukturę danych, taką jak tablica, lista itp.

Ciągła alokacja pamięci ma wiele implementacji w rzeczywistych zastosowaniach, takich jak system operacyjny w komputerach, systemy zarządzania bazami danych itp. Ta struktura danych jest uważana za elastyczną, ponieważ dodanie nowego punktu danych do tablicy wymaga tylko jednej jednostki czasu, tj.; O(1).

Ale problem pojawia się, gdy chcemy spojrzeć na konkretny wpis lub wyszukać konkretny wpis, ponieważ wszystkie rzeczywiste aplikacje polegają na poleceniach dostępu do danych. A to zadanie musi być wystarczająco szybkie, aby sprostać szybkości procesora i pamięci.

Istnieją różne algorytmy wyszukiwania podzielone na podstawie liczby porównań, które wykonujemy w celu przeszukania elementu.

Jeśli porównamy każdy punkt danych w tablicy, aby przeszukać element, zostanie to uznane za wyszukiwanie sekwencyjne. Ale jeśli porównujemy tylko kilka elementów, pomijając niektóre porównania, to jest to uważane za wyszukiwanie przedziałowe. Ale potrzebujemy tablicy w porządku posortowanym (w porządku rosnącym lub malejącym), aby przeprowadzić na niej wyszukiwanie interwałowe.

Złożoność czasowa wyszukiwania sekwencyjnego jest liniowa O(n), a złożoność czasowa wyszukiwania binarnego (przykład wyszukiwania przedziałowego) wynosi O(log n). Istnieją również inne algorytmy wyszukiwania, takie jak wyszukiwanie wykładnicze, wyszukiwanie z przeskokiem itp.

Jednak wyszukiwanie liniowe i wyszukiwanie binarne są używane głównie, gdzie wyszukiwanie liniowe dotyczy losowych lub nieposortowanych danych, a wyszukiwanie binarne dotyczy posortowanych i uporządkowanych danych. Haszowanie to specjalny algorytm wyszukiwania, w którym złożoność czasowa dostępu do punktu danych wynosi O(1).

Przyjrzyjmy się najpierw algorytmom wyszukiwania liniowego i wyszukiwania binarnego, a następnie porównajmy różnice między wyszukiwaniem liniowym a wyszukiwaniem binarnym.

Wyszukiwanie liniowe

Jak już wspomniano, algorytm wyszukiwania liniowego porównuje każdy element w tablicy, a oto kod, który to robi.

klasa publiczna uaktualnienie {
 public static int linear_search ( int [] arr, int n, int k){
 dla ( int i= 0 ; i<n; i++)
 jeśli (arr[i]==k)
 powrót i + 1 ;
 powrót – 1 ;
 }
 public static void main (String[] args){
 int [] arr= nowy int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 int k= 13 ;
 int n=arr.długość;
 int r=linear_search(arr, n, k);
 jeśli (r==- 1 )
 System.out.println( „nie znaleziono elementu” );
 w przeciwnym razie
 System.out.println( „element znaleziony w pozycji „ +r+ ” );
 }
 }

Przejdźmy przez kod.

Zadeklarowaliśmy funkcję linear_search, która jako parametry oczekuje tablicy, klucza liczb całkowitych. Teraz musimy zapętlić wszystkie elementy i porównać, czy pasuje do naszego klucza wyszukiwania, więc napisaliśmy pętlę for, która zapętla się po tablicy, a wewnątrz niej jest pętla if, która sprawdza, czy liczba na tej pozycji jest zgodna z klawiszem wyszukiwania, czy nie. Jeśli znajdziemy dopasowanie, zwrócimy pozycję. Jeśli nie ma takiego elementu w tablicy, zwrócimy -1 na końcu funkcji.

Zauważ, że jeśli mamy wiele wystąpień tej samej liczby, zwrócimy pozycję pierwszego wystąpienia.

Przechodząc do metody main, zadeklarowaliśmy i zainicjowaliśmy tablicę liczb całkowitych. Następnie inicjujemy klucz, który należy przeszukać. Tutaj zakodujemy tablicę i klucz, ale możesz to zmienić na dane wejściowe użytkownika. Teraz, gdy mamy już listę elementów i klucz do przeszukania, wywoływana jest metoda wyszukiwania liniowego i odnotowywany jest zwrócony indeks. Później sprawdzamy zwróconą wartość i wyświetlamy indeks, jeśli klucz istnieje, w przeciwnym razie nie znaleziono klucza.

Wyszukiwanie binarne

Wyszukiwanie binarne jest bardziej zoptymalizowane niż wyszukiwanie liniowe, ale tablica musi być posortowana, aby zastosować wyszukiwanie binarne. A oto kod, jak to zrobić.

klasa publiczna uaktualnienie {
 public static int binary_search ( int [] arr, int k){
 int l= 0 ,h=arr.length- 1 ,mid= 0 ;
 podczas gdy (l<=h){
 mid=l+(hl)/ 2 ;
 jeśli (arr[średnia]==k)
 powrót mid+ 1 ;
 inaczej if (arr[mid]>k)
 h=środek- 1 ;
 w przeciwnym razie
 l=średni+ 1 ;
 }
 powrót – 1 ;
 }
 public static void main (String[] args){
 int [] arr= nowy int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 int k= 8 ;
 int r=binarne_search(arr,k);
 jeśli (r==- 1 )
 System.out.println( „nie znaleziono elementu” );
 w przeciwnym razie
 System.out.println( „element znaleziony w pozycji „ +r+ ” );
 }
 }

Przejdźmy przez kod.

Zadeklarowaliśmy metodę binary_search, która oczekuje jako parametrów tablicy posortowanych liczb całkowitych i klucza liczb całkowitych. Inicjujemy zmienne low, high, mid. Tutaj niski, wysoki to wskaźniki, gdzie niski będzie przy indeksie 0, a wysoki będzie przy indeksie n na początku. Jak działa wyszukiwanie binarne?

Najpierw obliczymy środek niskiego i wysokiego. Średnią wartość możemy obliczyć jako (niski+wysoki)/2, ale czasami wysokość może być dużą liczbą, a dodanie do niej wartości niskiej może prowadzić do przepełnienia liczby całkowitej. Zatem obliczenie mida jako low+(high-low)/2 byłoby optymalnym sposobem.

Porównamy element w środku z kluczem wyszukiwania i zwrócimy indeks, jeśli znajdziemy dopasowanie. W przeciwnym razie sprawdzimy, czy środkowy element jest większy niż klucz, czy mniejszy niż klucz. Jeśli mid jest większy, musimy sprawdzić tylko pierwszą połowę tablicy, ponieważ wszystkie elementy w drugiej połowie tablicy są większe niż klucz, więc zaktualizujemy high do mid-1.

Podobnie, jeśli mid jest mniejszy niż klucz, musimy przeszukać drugą połowę tablicy, stąd aktualizując low do mid+1. Pamiętaj, że wyszukiwanie binarne opiera się na algorytmie zmniejszania i podbijania, ponieważ ignorujemy jedną z połówek tablicy w każdej iteracji.

Wracając do naszego kodu, zbudowaliśmy główną metodę. Zainicjowała posortowaną tablicę i klucz wyszukiwania, wywołała wyszukiwanie binarne i wydrukowała wyniki.

Teraz, gdy omówiliśmy algorytmy wyszukiwania liniowego i wyszukiwania binarnego, porównajmy oba algorytmy.

Wyszukiwanie liniowe a wyszukiwanie binarne

Pracujący

  • Wyszukiwanie liniowe iteruje wszystkie elementy i porównuje je z kluczem, który ma zostać przeszukany.
  • Wyszukiwanie binarne mądrze zmniejsza rozmiar tablicy, którą należy przeszukać i za każdym razem porównuje klucz z elementem środkowym.

Struktura danych

  • Wyszukiwanie liniowe jest elastyczne we wszystkich strukturach danych, takich jak tablica, lista, lista połączona itp.
  • Nie można przeprowadzić wyszukiwania binarnego na wszystkich strukturach danych, ponieważ potrzebujemy wielokierunkowego przechodzenia. Dlatego nie można używać struktur danych, takich jak pojedyncza połączona lista.

Warunki wstępne

  • Wyszukiwanie liniowe można przeprowadzić na wszystkich typach danych, dane mogą być losowe lub posortowane, algorytm pozostaje ten sam. Nie ma więc potrzeby wykonywania żadnych prac wstępnych.
  • Wyszukiwanie binarne działa tylko na posortowanej tablicy. Tak więc sortowanie tablicy jest warunkiem wstępnym dla tego algorytmu.

Przypadek użycia

  • Wyszukiwanie liniowe jest generalnie preferowane w przypadku mniejszych i losowo uporządkowanych zestawów danych.
  • Wyszukiwanie binarne jest preferowane w przypadku stosunkowo większych i posortowanych zestawów danych.

Skuteczność

  • Wyszukiwanie liniowe jest mniej wydajne w przypadku większych zbiorów danych.
  • Wyszukiwanie binarne jest bardziej wydajne w przypadku większych zbiorów danych.

Złożoność czasu

  • W wyszukiwaniu liniowym złożoność w najlepszym przypadku to O(1), w której element znajduje się w pierwszym indeksie. Złożoność najgorszego przypadku to O(n), gdzie element znajduje się pod ostatnim indeksem lub element nie występuje w tablicy.
  • W wyszukiwaniu binarnym złożoność w najlepszym przypadku to O(1), gdzie element znajduje się w środkowym indeksie. Złożoność najgorszego przypadku to O( log 2 n).

Próba

Załóżmy, że mamy tablicę o rozmiarze 10 000.

  • W wyszukiwaniu liniowym złożoność najlepszego przypadku to O(1), a złożoność najgorszego przypadku to O(10000).
  • W wyszukiwaniu binarnym złożoność najlepszego przypadku wynosi O(1), a złożoność najgorszego przypadku wynosi O( log 2 10000)=O(13.287).

Wniosek

Zrozumieliśmy znaczenie dostępu do danych w tablicach, zrozumieliśmy algorytmy wyszukiwania liniowego i wyszukiwania binarnego. Przeszedł przez kody wyszukiwania liniowego i wyszukiwania binarnego. Porównanie różnic między wyszukiwaniem liniowym a wyszukiwaniem binarnym, wykonane na sucho dla dużego przykładu.

Teraz, gdy już wiesz o różnicach między wyszukiwaniem liniowym a wyszukiwaniem binarnym, spróbuj uruchomić oba kody dla dużego zestawu danych wielopoziomowych i porównaj czas wykonania, zacznij eksplorować różne algorytmy wyszukiwania i spróbuj je zaimplementować!

Jeśli jesteś zainteresowany nauką o danych, sprawdź IIIT-B i upGrad's PG Diploma in Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1- on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.

Ucz się online kursów nauki o danych z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

Porównaj wyszukiwanie liniowe i wyszukiwanie binarne przy użyciu ich złożoności.

Wyszukiwanie binarne jest pod wieloma względami bardziej zoptymalizowane i wydajne niż wyszukiwanie liniowe, zwłaszcza gdy elementy są posortowane. Powód sprowadza się do złożoności obu poszukiwań.
Wyszukiwanie liniowe
1. Złożoność czasowa: O(N) - Ponieważ w wyszukiwaniu liniowym przechodzimy przez tablicę, aby sprawdzić, czy jakiś element pasuje do klucza. W najgorszym przypadku element będzie obecny na końcu tablicy, więc musimy przejść przez koniec, a zatem złożoność czasowa będzie wynosić O(N), gdzie N jest całkowitą liczbą elementów tablicy.
2. Złożoność przestrzeni: O(1) — Nie używamy dodatkowej przestrzeni, więc złożoność przestrzeni będzie wynosić O(1).
Wyszukiwanie binarne
1. Złożoność czasowa: O(log N) — w wyszukiwaniu binarnym wyszukiwanie zmniejsza się o połowę, ponieważ wystarczy spojrzeć do środka tablicy. I ciągle skracamy nasze poszukiwania do środka sekcji, w której występuje dany pierwiastek.
2. Złożoność przestrzeni: O(1)
- Nie używamy dodatkowej przestrzeni, więc złożoność przestrzeni będzie O(1).

Czy istnieje inna metoda wyszukiwania elementu w tablicy?

Chociaż wyszukiwanie liniowe i wyszukiwanie binarne są często używane do wyszukiwania, rzeczywiście istnieje inna metoda wyszukiwania - metoda interpolacji. Jest to zoptymalizowana wersja wyszukiwania binarnego, w której wszystkie elementy są rozmieszczone równomiernie.
Ideą tej metody jest to, że w wyszukiwaniu binarnym zawsze szukamy środka tablicy. Ale w tej metodzie wyszukiwanie może przejść do różnych lokalizacji w zależności od tego, gdzie znajduje się klucz. Na przykład, jeśli klucz znajduje się w pobliżu ostatniego elementu tablicy, wyszukiwanie rozpocznie się od końca tablicy.

Jakie są różne złożoności czasowe wyszukiwania interpolacyjnego?

Najgorsza złożoność czasowa wyszukiwania interpolacyjnego wynosi O(N), ponieważ w najgorszym przypadku klucz będzie znajdował się na końcu tablicy, więc iterator musi przejść przez całą tablicę.
Średnia złożoność przypadku będzie wynosić O(log(log N), ponieważ element może znajdować się w dowolnym miejscu tablicy.Może również znajdować się w pobliżu punktu początkowego.
Złożoność w najlepszym przypadku będzie wynosić O(1), ponieważ w najlepszym przypadku klucz będzie pierwszym elementem tablicy.