Binarno iskanje je ena od tehnik iskanja, ki se uporablja, ko je vnos razvrščen. Tukaj se osredotočamo na iskanje srednjega elementa, ki deluje kot referenčni okvir, ne glede na to, ali gremo levo ali desno do njega, saj so elementi že razvrščeni. To iskanje pomaga optimizirati tehniko iskanja z vsako ponovitvijo, imenujemo ga binarno iskanje in bralci ga poudarjajo, saj se posredno uporablja pri reševanju vprašanj.
Binarni iskalni algoritem v Javi
Spodaj je algoritem, zasnovan za binarno iskanje:
- Začetek
- Vzemite vhodno polje in cilj
- Inicializiraj začetek = 0 in konec = (velikost polja -1)
- Indijaniziraj srednjo spremenljivko
- sredina = (začetek+konec)/2
- if array[ mid ] == target then return mid
- če niz [sredina]
- if array[ mid ]> target then end = mid-1
- če je začetek<=konec, pojdite na 5. korak
- vrni -1 kot Element ni bil najden
- Izhod
Zdaj gotovo razmišljate, kaj če vnos ni razvrščen, so rezultati nedefinirani.
Opomba: Če obstajajo dvojniki, ni nobenega zagotovila, kateri bo najden.
Metode za binarno iskanje v Javi
V Javi obstajajo tri metode za implementacijo Binarno iskanje v Javi so omenjeni spodaj:
- Iterativna metoda
- Rekurzivna metoda
- Metoda vgradnje
1. Iterativna metoda za binarno iskanje v Javi
Spodaj je izvedba navedena spodaj:
Java
// 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);> >}> }> |
>
>Izhod
java vsebuje podniz
Element found at index 3>
Nasvet: Geeki se gotovo sprašujete, ali obstaja kakšna podobna funkcija spodnja_meja() oz Zgornja meja() najverjetneje v C++ STL. tako da je jasen odgovor, da funkcije ni bilo samo do Jave 9, kasneje so bile dodane.
2. Rekurzivna metoda za binarno iskanje
Spodaj je izvedba zgornje metode:
Java
// 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);> >}> }> |
>
>Izhod
Element is present at index 3>
Kompleksnost zgornje metode
Časovna zapletenost: O(log N)
Kompleksnost prostora: O(1), če se upošteva rekurzivni klicni sklad, bo pomožni prostor O(log N)
3. V metodi gradnje za binarno iskanje v Javi
Arrays.binarysearch() deluje tudi za nize, ki so lahko primitivnega podatkovnega tipa.
Spodaj je izvedba zgornje metode:
Java
// 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'>);> >}> }> |
>
>Izhod
22 found at index = 3 40 Not found>
Binarno iskanje v zbirkah Java
Zdaj pa si poglejmo, kako deluje Collections.binarySearch() za LinkedList. Tako v bistvu, kot je razloženo zgoraj, se ta metoda izvaja v log(n) času za seznam z naključnim dostopom, kot je ArrayList. Če podani seznam ne izvaja vmesnika RandomAccess in je velik, bo ta metoda izvedla binarno iskanje na podlagi iteratorja, ki izvede O(n) prehodov povezav in O(log n) primerjav elementov.
Zbirke.binarysearch() deluje za predmete, kot so zbirke ArrayList in LinkedList .
Spodaj je izvedba zgornje metode:
Java
// 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'>);> >}> }> |
>
>Izhod
10 found at index = 3 15 Not found>
Kompleksnost zgornje metode
Časovna zapletenost : O(log N)
Pomožni prostor : O(1)