Algorytm wyszukiwania binarnego w Javie

1. Przegląd

W tym artykule omówimy zalety wyszukiwania binarnego w porównaniu z prostym wyszukiwaniem liniowym i omówimy jego implementację w Javie.

2. Potrzeba wydajnego wyszukiwania

Powiedzmy, że zajmujemy się sprzedażą win i codziennie miliony kupujących odwiedzają naszą aplikację.

Dzięki naszej aplikacji klient może odfiltrować artykuły o cenie poniżej n dolarów, wybrać butelkę z wyników wyszukiwania i dodać ją do swojego koszyka. Mamy miliony użytkowników poszukujących win z limitem cenowym co sekundę. Wyniki muszą być szybkie.

Na zapleczu nasz algorytm przeprowadza liniowe przeszukiwanie całej listy win, porównując limit ceny wprowadzony przez klienta z ceną każdej butelki wina na liście.

Następnie zwraca przedmioty, których cena jest niższa lub równa limitowi ceny. To wyszukiwanie liniowe ma złożoność czasową O (n) .

Oznacza to, że im większa liczba butelek wina w naszym systemie, tym więcej czasu to zajmie. Czas wyszukiwania rośnie proporcjonalnie do liczby wprowadzonych nowych pozycji.

Jeśli zaczniemy zapisywać elementy w kolejności posortowanej i wyszukujemy elementy przy użyciu wyszukiwania binarnego, możemy osiągnąć złożoność O (log n) .

W przypadku wyszukiwania binarnego czas potrzebny na wyniki wyszukiwania naturalnie zwiększa się wraz z rozmiarem zbioru danych, ale nie proporcjonalnie.

3. Wyszukiwanie binarne

Mówiąc najprościej, algorytm porównuje wartość klucza ze środkowym elementem tablicy; jeśli są nierówne, połowa, w której klucz nie może być częścią, jest eliminowana, a poszukiwanie jest kontynuowane przez pozostałą połowę, aż się powiedzie.

Pamiętaj - kluczowym aspektem jest to, że tablica jest już posortowana.

Jeśli wyszukiwanie kończy się, a pozostała połowa jest pusta, klucza nie ma w tablicy.

3.1. Iteracyjny Impl

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

Metoda runBinarySearchIteratives przyjmuje jako argumenty sortowaną tablicę , klucz oraz niskie i wysokie indeksy sortowanej tablicy . Gdy metoda jest uruchamiana po raz pierwszy, najniższy , pierwszy indeks sortowanej tablicy jest równy 0, natomiast najwyższy , ostatni indeks sortowanej tablicy, jest równy jego długości - 1.

Środkowy jest średnim wskaźnikiem sortedArray . Teraz algorytm prowadzi while pętli porównujący klucza z wartością tablicy środkowej indeks sortedArray .

3.2. Rekurencyjne Impl

Przyjrzyjmy się teraz również prostej, rekurencyjnej implementacji:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

RunBinarySearchRecursively sposób przyjmuje sortedArray , klucz, na niskie i wysokie indeksy sortedArray .

3.3. Korzystanie z tablic. binarySearch ()

int index = Arrays.binarySearch(sortedArray, key); 

SortArray i klucz int , który ma być przeszukiwany w tablicy liczb całkowitych, są przekazywane jako argumenty do metody binarySearch klasy Java Arrays .

3.4. Korzystanie z kolekcji. binarySearch ()

int index = Collections.binarySearch(sortedList, key); 

SortList i klucz Integer , który ma być przeszukiwany na liście obiektów Integer , są przekazywane jako argumenty do metody binarySearch klasy Java Collections .

3.5. Wydajność

To, czy użyć podejścia rekurencyjnego, czy iteracyjnego do pisania algorytmu, jest głównie kwestią osobistych preferencji. Ale nadal jest kilka punktów, o których powinniśmy wiedzieć:

1. Rekurencja może być wolniejsza ze względu na obciążenie związane z utrzymaniem stosu i zwykle zajmuje więcej pamięci

2. Rekurencja nie jest przyjazna dla stosu . Może to spowodować wyjątek StackOverflowException podczas przetwarzania dużych zbiorów danych

3. Rekursja zwiększa przejrzystość kodu, ponieważ sprawia, że ​​jest on krótszy w porównaniu z podejściem iteracyjnym

Idealnie byłoby, gdyby wyszukiwanie binarne wykonało mniejszą liczbę porównań w porównaniu do wyszukiwania liniowego dla dużych wartości n. W przypadku mniejszych wartości n wyszukiwanie liniowe może działać lepiej niż wyszukiwanie binarne.

Należy wiedzieć, że ta analiza jest teoretyczna i może się różnić w zależności od kontekstu.

Ponadto algorytm wyszukiwania binarnego wymaga posortowanego zestawu danych, który również ma swoje koszty . Jeśli do sortowania danych użyjemy algorytmu sortowania przez scalanie, do naszego kodu zostanie dodana dodatkowa złożoność n log n .

Dlatego najpierw musimy dobrze przeanalizować nasze wymagania, a następnie podjąć decyzję, który algorytm wyszukiwania będzie najlepiej odpowiadał naszym wymaganiom.

4. Wniosek

W tym samouczku przedstawiono implementację algorytmu wyszukiwania binarnego i scenariusz, w którym lepiej byłoby go użyć zamiast wyszukiwania liniowego.

Znajdź kod do samouczka na GitHub.