Arrays.binarySearch() menetelmä etsii tietyn tietotyypin määritetystä taulukosta määritettyä arvoa käyttämällä binaarihakualgoritmia. Taulukko on lajiteltava kuten Arrays.sort() menetelmää ennen tämän puhelun soittamista. Jos sitä ei ole lajiteltu, tulokset ovat määrittelemättömiä. Jos taulukko sisältää useita elementtejä määritetyllä arvolla, ei ole takeita, mikä niistä löytyy. Liukuvaamme alla olevan kuvan läpi seuraavasti.
Kuva:
Searching for 35 in byteArr[] = {10,20,15,22,35} will give result as 4 as it is the index of 35 Searching for g in charArr[] = {'g','p','q','c','i'} will give result as 0 as it is the index of 'g' Searching for 22 in intArr[] = {10,20,15,22,35}; will give result as 3 as it is the index of 22 Searching for 1.5 in doubleArr[] = {10.2,15.1,2.2,3.5} will give result as -1 as it is the insertion point of 1.5 Searching for 35.0 in floatArr[] = {10.2f,15.1f,2.2f,3.5f} will give result as -5 as it is the insertion point of 35.0 Searching for 5 in shortArr[] = {10,20,15,22,35} will give result as -1 as it is the insertion point of 5> Se on yksinkertaisin ja tehokkain tapa löytää elementti lajitetusta taulukosta Javassa
Syntaksi:
public static int binarySearch(data_type arr, data_type key)>
Muistaa: Tässä tietotyyppi voi olla mikä tahansa primitiivisistä tietotyypeistä, kuten tavu, char, double, int, float, lyhyt, pitkä ja jopa objekti.
Parametrit:
- Haettava joukko
- Haettava arvo
Palautustyyppi: hakuavaimen indeksi, jos se sisältyy taulukkoon; muussa tapauksessa (-(lisäyskohta) – 1). Lisäyskohta määritellään pisteeksi, jossa avain lisättäisiin taulukkoon: ensimmäisen elementin indeksi on suurempi kuin avain tai a.length, jos kaikki taulukon elementit ovat pienempiä kuin määritetty avain. Huomaa, että tämä takaa, että palautusarvo on>= 0, jos ja vain jos avain löytyy.
On joitakin tärkeitä asioita, jotka on pidettävä mielessä seuraavasti:
- Jos syöttöluetteloa ei ole lajiteltu, tulokset ovat määrittelemättömiä.
- Jos on kaksoiskappaleita, ei ole takeita, kumpi niistä löytyy.
Kuten edellä olemme jo keskustelleet, että voimme käyttää tätä algoritmia joko Arrays.binarysearch() vs Collections.binarysearch() . Arrays.binarysearch() toimii taulukoille, jotka voivat olla myös primitiivistä tietotyyppiä. Kokoelmat .binarysearch() toimii objekteille Kokoelmat, kuten ArrayList ja LinkedList .
Esimerkki 1:
Java
tkinter-painiketta
// Java program to demonstrate working of Arrays.> // binarySearch() in a sorted array> // Importing Arrays class from> // java.util package> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring and initializing byte arrays> >// to search over them> >byte> byteArr[] = {>10>,>20>,>15>,>22>,>35> };> >char> charArr[] = {>'g'>,>'p'>,>'q'>,>'c'>,>'i'> };> >int> intArr[] = {>10>,>20>,>15>,>22>,>35> };> >double> doubleArr[] = {>10.2>,>15.1>,>2.2>,>3.5> };> >float> floatArr[] = {>10>.2f,>15>.1f,>2>.2f,>3>.5f };> >short> shortArr[] = {>10>,>20>,>15>,>22>,>35> };> >// Using sort() method of Arrays class> >// and passing arrays to be sorted as in arguments> >Arrays.sort(byteArr);> >Arrays.sort(charArr);> >Arrays.sort(intArr);> >Arrays.sort(doubleArr);> >Arrays.sort(floatArr);> >Arrays.sort(shortArr);> >// Primitive datatypes> >byte> byteKey =>35>;> >char> charKey =>'g'>;> >int> intKey =>22>;> >double> doubleKey =>1.5>;> >float> floatKey =>35>;> >short> shortKey =>5>;> >// Now in sorted array we will fetch and> >// return elements/indiciesaccessing indexes to show> >// array is really sorted> >// Print commands where we are implementing> >System.out.println(> >byteKey +>' found at index = '> >+ Arrays.binarySearch(byteArr, byteKey));> >System.out.println(> >charKey +>' found at index = '> >+ Arrays.binarySearch(charArr, charKey));> >System.out.println(> >intKey +>' found at index = '> >+ Arrays.binarySearch(intArr, intKey));> >System.out.println(> >doubleKey +>' found at index = '> >+ Arrays.binarySearch(doubleArr, doubleKey));> >System.out.println(> >floatKey +>' found at index = '> >+ Arrays.binarySearch(floatArr, floatKey));> >System.out.println(> >shortKey +>' found at index = '> >+ Arrays.binarySearch(shortArr, shortKey));> >}> }> |
>
>Lähtö
35 found at index = 4 g found at index = 1 22 found at index = 3 1.5 found at index = -1 35.0 found at index = -5 5 found at index = -1>
Monimutkaisuusanalyysi:
Aika monimutkaisuus:
Arrays.binarySearch()-menetelmän aikamonimutkaisuus on O(log n), jossa n on syötetaulukon pituus. Tämä johtuu siitä, että menetelmä käyttää binäärihakualgoritmia löytääkseen kohdeelementin lajitetusta taulukosta.
Aputila:
Arrays.binarySearch()-menetelmän käyttämä aputila on O(1), koska se ei vaadi muuta ylimääräistä tilaa kuin syötetaulukon hakutoiminnon suorittamiseen.
Tästä menetelmästä on olemassa muunnelmia, joissa voimme myös määrittää etsittävän taulukon alueen. Keskustelemme siitä samoin kuin etsimisestä Object-taulukosta muissa viesteissä.
Esimerkki 2:
lisää merkkijono java
Java
rj12 vs rj11
// Java Program to Illustrate 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 empty List> >List al =>new> ArrayList();> >// Adding elements to the List> >al.add(>12>);> >al.add(>53>);> >al.add(>23>);> >al.add(>46>);> >al.add(>54>);> >// Using binarySearch() method of Collections class> >// over random inserted element and storing the> >// index> >int> index = Collections.binarySearch(al,>23>);> >// Print and display the index> >System.out.print(index);> >}> }> |
>
>Lähtö
2>
Monimutkaisuusanalyysi:
Aika monimutkaisuus:
Kokoelmat-luokan binarySearch()-metodin aikamonimutkaisuus on O(log n), jossa n on listan elementtien lukumäärä.
Aputila:
Kokoelmat-luokan binarySearch()-metodi ei vaadi ylimääräistä tilaa, joten sen aputilan monimutkaisuus on O(1).