Wyszukiwanie liniowe w Javie zawsze było podstawową metodą znajdowania elementu w tablicy. Przeszukuje sekwencyjnie każdy element tablicy i jest niezwykle łatwy do wdrożenia. Jednak wady wyszukiwania liniowego są oczywiste, gdy dana tablica zawiera dziesiątki tysięcy elementów. W takich przypadkach metoda „dziel i rządź” wdrożona przez Binary Search jest o wiele bardziej wydajna i preferowana dla programistów z myślą o złożoności czasowej i przestrzennej.
Wyszukiwanie binarne
W wyszukiwaniu binarnym tablica jest wielokrotnie dzielona na dwie połowy, dopóki nie zostanie znaleziony klucz (przeszukiwany element). Podział jest wirtualny, tzn. zachowana jest integralność danych. Przy każdej iteracji skupiana jest środkowa wartość tablicy. Jeśli wartość jest równa kluczowi, którego szukamy, pętla lub funkcja rekurencyjna kończy się. W przeciwnym razie zapętla się dalej. Jeśli środkowa wartość jest większa niż klucz, funkcja koncentruje się na pierwszej połowie tablicy i odwrotnie. Ten proces jest powtarzany, dopóki klucz nie zostanie znaleziony lub cała tablica nie zostanie powtórzona.
Różnica między wyszukiwaniem liniowym a binarnym
Wyszukiwanie liniowe |
Wyszukiwanie binarne |
Sekwencyjnie przeszukuje tablicę |
Dzieli tablicę na dwie połowy, aż do znalezienia wartości |
Działa z dowolną macierzą |
Działa tylko z posortowanymi tablicami |
Złożoność to O(N) |
Złożoność to O(log2N) |
Może pracować na posortowanych i nieposortowanych tablicach |
Można zaimplementować tylko na posortowanych tablicach. |
Mniej skomplikowane do wdrożenia |
Bardziej złożony do wdrożenia |
Algorytm wyszukiwania binarnego
Algorytm wyszukiwania binarnego podano poniżej.
- Wyznacz pierwszy i ostatni punkt tablicy. Punkty będą dostosowywane przy każdej iteracji zgodnie z tablicą i wyszukiwanym kluczem.
- Przejrzyj tablicę i porównaj środkową wartość między bieżącym pierwszym a ostatnim punktem. W pierwszej iteracji pierwsza i ostatnia zmienna będą takie same jak rzeczywiste zmienne w tablicy.
- Jeśli klucz jest większy niż wartość środkowa, indeks tej wartości zostanie zapisany w nowej zmiennej „Pierwsza”.
- Jeśli klucz jest mniejszy niż wartość środkowa, indeks tej wartości zostanie zapisany w zmiennej „Ostatnia”.
- Warunek ten jest powtarzany, aż spełni się jeden z dwóch warunków:
- Znaleziono klucz.
- Cała tablica została powtórzona.
Kod dla iteracyjnego wyszukiwania binarnego i rekurencyjnego wyszukiwania binarnego podano poniżej.
Iteracyjne wyszukiwanie binarne
Poniżej podano kod wyszukiwania binarnego z metodą iteracyjną.
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
int start = 0;
int end = arr.length;
for(int i = 0; iarr[n]){
start = n;
}
else{
end = n;
}
}
return -1;
}
}
Rekurencyjne wyszukiwanie binarne
Kod dla Binary przy użyciu rekurencji podano poniżej.
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
if(arr[n]==num)
return n;
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
Złożoność czasu
Z każdą kolejną iteracją tablica, czyli przestrzeń wyszukiwania, jest dzielona na pół. Po każdej iteracji „m” przestrzeń poszukiwań zmieni się na rozmiar N/2m. W najgorszym przypadku pozostanie nam tylko jeden element po jednej odległej stronie tablicy. W tej chwili złożoność wyszukiwania binarnego wyniesie k = log2N. Złożoność czasowa wyszukiwania liniowego wynosi O(N), co powoduje, że wyszukiwanie binarne jest znacznie szybsze przy złożoności O(log2N). Jest to główna zaleta korzystania z wyszukiwania binarnego w porównaniu z wyszukiwaniem liniowym.
Złożoność przestrzeni
Wyszukiwanie binarne wykorzystuje trzy różne zmienne — początek, koniec i środek. Te trzy zmienne są tworzone jako wskaźniki wskazujące miejsce w pamięci indeksów tablicy. Z tego powodu wyszukiwanie binarne jest niezwykle wydajne z przestrzenią. Złożoność przestrzenna iteracyjnego wyszukiwania binarnego wynosi O(1). W przypadku implementacji rekurencyjnej jest to O (log N).