Binäärihaku on yksi hakutekniikoista, joita käytetään syötettä lajitettaessa. Tässä keskitymme löytämään keskimmäinen elementti, joka toimii viitekehyksenä, mennäänkö siihen vasemmalle vai oikealle, koska elementit on jo lajiteltu. Tämä haku auttaa optimoimaan hakutekniikkaa jokaisella iteraatiolla, ja sitä kutsutaan binäärihauksi ja lukijat stressaavat siitä, koska sitä sovelletaan epäsuorasti kysymysten ratkaisemiseen.
Binäärihakualgoritmi Javassa
Alla on binäärihakuun suunniteltu algoritmi:
- alkaa
- Ota syöttötaulukko ja kohde
- Alusta alku = 0 ja loppu = (taulukon koko -1)
- Intialise mid variable
- puoliväli = (alku+loppu)/2
- jos array[ mid ] == kohde sitten return mid
- jos array[ mid ]
- jos array[ mid ]> target sitten end = mid-1
- jos alku<=loppu, siirry vaiheeseen 5
- palauttaa -1 nimellä Ei elementtiä löytynyt
- Poistu
Nyt sinun täytyy miettiä, mitä jos syötettä ei lajitella, tulokset ovat määrittelemättömiä.
Huomautus: Jos on kaksoiskappaleita, ei ole takeita, kumpi niistä löytyy.
Java-binaarihaun menetelmät
Javassa on kolme toteutustapaa Binäärihaku Javassa on mainittu alla:
- Iteratiivinen menetelmä
- Rekursiivinen menetelmä
- Sisäänrakennettu menetelmä
1. Iteratiivinen menetelmä Java-binäärihakuun
Alla on mainittu toteutus:
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);> >}> }> |
>
>Lähtö
shilpa shetty ikä
Element found at index 3>
Kärki: Geeks sinun täytyy ihmetellä, onko olemassa mitään toimintoa, kuten alaraja() tai yläraja() Löytyy todennäköisesti C++ STL:stä. joten suora vastaus on, että toimintoa ei ollut vain Java 9: een asti, myöhemmin ne lisättiin.
2. Rekursiivinen menetelmä binäärihakuun
Alla on yllä olevan menetelmän toteutus:
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);> >}> }> |
>
>Lähtö
Element is present at index 3>
Yllä olevan menetelmän monimutkaisuus
Aika monimutkaisuus: O(log N)
Tilan monimutkaisuus: O(1), Jos otetaan huomioon rekursiivinen kutsupino, aputila on O(log N)
3. Kohdassa Build Method for Binary Search Javassa
Arrays.binarysearch() toimii taulukoille, jotka voivat olla myös primitiivistä tietotyyppiä.
Alla on yllä olevan menetelmän toteutus:
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'>);> >}> }> |
>
>Lähtö
22 found at index = 3 40 Not found>
Binäärihaku Java-kokoelmissa
Katsotaan nyt, kuinka Collections.binarySearch() toimii LinkedListissä. Joten periaatteessa, kuten edellä on käsitelty, tämä menetelmä toimii log(n)-ajassa hajasaantiluettelossa, kuten ArrayList. Jos määritetty luettelo ei toteuta RandomAccess-liitäntää ja on suuri, tämä menetelmä tekee iteraattoripohjaisen binäärihaun, joka suorittaa O(n) linkin läpikulkua ja O(log n) elementtivertailua.
Collections.binarysearch() toimii objekteille Kokoelmat kuten ArrayList ja LinkedList .
Alla on yllä olevan menetelmän toteutus:
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'>);> >}> }> |
>
>Lähtö
10 found at index = 3 15 Not found>
Yllä olevan menetelmän monimutkaisuus
Aika monimutkaisuus : O(log N)
Aputila : O(1)