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
wypisz Java do tablicy
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
10 found at index = 3 15 Not found>
Złożoność powyższej metody
Złożoność czasowa : O(log N)
Przestrzeń pomocnicza : O(1)