WYSZUKIWANIE BINARNE W JAVIE

Wyszukiwanie binarne jest jedną z technik wyszukiwania stosowanych podczas sortowania danych wejściowych. Tutaj skupiamy się na znalezieniu środkowego elementu, który działa jako ramka odniesienia, niezależnie od tego, czy przejść do niego w lewo, czy w prawo, ponieważ elementy są już posortowane. Wyszukiwanie to pomaga w optymalizacji techniki wyszukiwania. Każda iteracja nazywa się wyszukiwaniem binarnym i czytelnicy kładą na to nacisk, ponieważ jest ono pośrednio stosowane przy rozwiązywaniu pytań.

Algorytm wyszukiwania binarnego w Javie

Poniżej znajduje się algorytm przeznaczony do wyszukiwania binarnego:

Początek

Weź tablicę wejściową i cel

Zainicjuj początek = 0 i koniec = (rozmiar tablicy -1)

Indyjska zmienna średnia

środek = (początek+koniec)/2

jeśli tablica [mid] == cel, zwróć środek

jeśli tablica [środek]

jeśli tablica [mid]> cel, to end = mid-1

jeśli start <=koniec, przejdź do kroku 5

zwróć -1 jako Nie znaleziono elementu

Wyjście

Teraz musisz się zastanowić, co się stanie, jeśli dane wejściowe nie zostaną posortowane, a wyniki będą niezdefiniowane.

Notatka: Jeśli istnieją duplikaty, nie ma gwarancji, który z nich zostanie znaleziony.

Metody wyszukiwania binarnego w Javie

W Javie istnieją trzy metody do wdrożenia Wyszukiwanie binarne w Javie są wymienione poniżej:

Metoda iteracyjna
Metoda rekurencyjna
Metoda wbudowania

1. Iteracyjna metoda wyszukiwania binarnego w Javie

Poniżej znajduje się implementacja wymieniona poniżej:

Jawa

// Java implementation of iterative Binary Search> class> BinarySearch {> > // Returns index of x if it is present in arr[l....r], else return -1> > int> binarySearch(> int> arr[],> int> l,> int> r,> int> x)> > {> > while> (l <= r) {> > int> mid = (l + r) /> 2> ;> > // If the element is present at the> > // middle itself> > if> (arr[mid] == x) {> > return> mid;> > // If element is smaller than mid, then> > // it can only be present in left subarray> > // so we decrease our r pointer to mid - 1> > }> else> if> (arr[mid]>x) {> > r = mid -> 1> ;> > // Else the element can only be present> > // in right subarray> > // so we increase our l pointer to mid + 1> > }> else> {> > l = mid +> 1> ;> > }> > }> > // We reach here when element is not present> > // in array> > return> -> 1> ;> > }> > // Driver method to test above> > public> static> void> main(String args[])> > {> > BinarySearch ob => new> BinarySearch();> > int> arr[] = {> 2> ,> 3> ,> 4> ,> 10> ,> 40> };> > int> n = arr.length;> > int> x => 10> ;> > int> result = ob.binarySearch(arr,> 0> , n -> 1> , x);> > if> (result == -> 1> )> > System.out.println(> 'Element not present'> );> > else> > System.out.println(> 'Element found at index '> > + result);> > }> }>

Wyjście

Element found at index 3

Wskazówka: Geekowie, z pewnością zastanawiacie się, czy istnieje taka funkcja Dolna granica() Lub Górna granica() prawdopodobnie znaleziony w C++ STL. więc prosta odpowiedź jest taka, że nie było żadnej funkcji aż do Java 9, później zostały dodane.

2. Metoda rekurencyjna wyszukiwania binarnego

Poniżej implementacja powyższej metody:

Jawa

// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> > // Returns index of x if it is present in arr[l..> > // r], else return -1> > int> binarySearch(> int> arr[],> int> l,> int> r,> int> x)> > {> > if> (r>= l) {> > int> mid = l + (r - l) /> 2> ;> > // If the element is present at the> > // middle itself> > if> (arr[mid] == x)> > return> mid;> > // If element is smaller than mid, then> > // it can only be present in left subarray> > if> (arr[mid]>x)> > return> binarySearch(arr, l, mid -> 1> , x);> > // Else the element can only be present> > // in right subarray> > return> binarySearch(arr, mid +> 1> , r, x);> > }> > // We reach here when element is not present> > // in array> > return> -> 1> ;> > }> > // main function> > public> static> void> main(String args[])> > {> > BinarySearch ob => new> BinarySearch();> > int> arr[] = {> 2> ,> 3> ,> 4> ,> 10> ,> 40> };> > int> n = arr.length;> > int> x => 10> ;> > int> result = ob.binarySearch(arr,> 0> , n -> 1> , x);> > if> (result == -> 1> )> > System.out.println(> > 'Element is not present in array'> );> > else> > System.out.println(> > 'Element is present at index '> + result);> > }> }>

Wyjście

Element is present at index 3

Złożoność powyższej metody

Złożoność czasowa: O(log N)
Złożoność przestrzeni: O(1), jeśli uwzględniony zostanie stos wywołań rekurencyjnych, wówczas przestrzeń pomocnicza będzie wynosić O(log N)

3. W metodzie budowania wyszukiwania binarnego w Javie

Tablice.binarysearch() działa dla tablic, które mogą być również prymitywnego typu danych.

Poniżej implementacja powyższej metody:

Jawa

// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> > // Main driver method> > public> static> void> main(String[] args)> > {> > // Declaring an integer array> > int> arr[] = {> 10> ,> 20> ,> 15> ,> 22> ,> 35> };> > // Sorting the above array> > // using sort() method of Arrays class> > Arrays.sort(arr);> > int> key => 22> ;> > int> res = Arrays.binarySearch(arr, key);> > if> (res>=> 0> )> > System.out.println(> > key +> ' found at index = '> + res);> > else> > System.out.println(key +> ' Not found'> );> > key => 40> ;> > res = Arrays.binarySearch(arr, key);> > if> (res>=> 0> )> > System.out.println(> > key +> ' found at index = '> + res);> > else> > System.out.println(key +> ' Not found'> );> > }> }>

Wyjście

22 found at index = 3 40 Not found

Wyszukiwanie binarne w kolekcjach Java

Zobaczmy teraz, jak Collections.binarySearch() działa w przypadku LinkedList. Zasadniczo, jak omówiono powyżej, ta metoda działa w czasie log(n) dla listy o swobodnym dostępie, takiej jak ArrayList. Jeśli określona lista nie implementuje interfejsu RandomAccess i jest duża, ta metoda wykona wyszukiwanie binarne oparte na iteratorze, które wykona przejścia łączy O(n) i porównania elementów O(log n).

Kolekcje.binarysearch() działa dla kolekcji obiektów takich jak Lista tablic I Połączona lista .

Poniżej implementacja powyższej metody:

Jawa

// Java Program to Demonstrate Working of binarySearch()> // method of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> > // Main driver method> > public> static> void> main(String[] args)> > {> > // Creating an empty ArrayList of integer type> > List al => new> ArrayList();> > // Populating the Arraylist> > al.add(> 1> );> > al.add(> 2> );> > al.add(> 3> );> > al.add(> 10> );> > al.add(> 20> );> > // 10 is present at index 3> > int> key => 10> ;> > int> res = Collections.binarySearch(al, key);> > if> (res>=> 0> )> > System.out.println(> > key +> ' found at index = '> + res);> > else> > System.out.println(key +> ' Not found'> );> > key => 15> ;> > res = Collections.binarySearch(al, key);> > if> (res>=> 0> )> > System.out.println(> > key +> ' found at index = '> + res);> > else> > System.out.println(key +> ' Not found'> );> > }> }>

Wyjście