Wyszukiwanie binarne w Javie: kolekcje rekurencyjne, iteracyjne i Java

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

Algorytm wyszukiwania binarnego

Algorytm wyszukiwania binarnego podano poniżej.

1. Wyznacz pierwszy i ostatni punkt tablicy. Punkty będą dostosowywane przy każdej iteracji zgodnie z tablicą i wyszukiwanym kluczem.
2. 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.
3. Jeśli klucz jest większy niż wartość środkowa, indeks tej wartości zostanie zapisany w nowej zmiennej „Pierwsza”.
4. Jeśli klucz jest mniejszy niż wartość środkowa, indeks tej wartości zostanie zapisany w zmiennej „Ostatnia”.
5. 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){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'               
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        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){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        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).