Arrays.binarySearch() metoda caută în matricea specificată a tipului de date dat pentru valoarea specificată folosind algoritmul de căutare binar. Matricea trebuie sortată după cum urmează Arrays.sort() metoda înainte de a efectua acest apel. Dacă nu este sortat, rezultatele sunt nedefinite. Dacă matricea conține mai multe elemente cu valoarea specificată, nu există nicio garanție care va fi găsit. Să trecem prin ilustrația de mai jos, după cum urmează.

Ilustrare:

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>

Este cea mai simplă și eficientă metodă de a găsi un element într-o matrice sortată în Java

Sintaxă:

public static int binarySearch(data_type arr, data_type key)>

Tine minte: Aici tipul de date poate fi oricare dintre tipurile de date primitive, cum ar fi byte, char, double, int, float, short, long și chiar obiect.

Parametri:

• Matricea care trebuie căutată
• Valoarea care trebuie căutată

Tip returnare: indexul cheii de căutare, dacă este conținută în matrice; în caz contrar, (-(punctul de inserare) – 1). Punctul de inserare este definit ca punctul în care cheia ar fi inserată în matrice: indexul primului element mai mare decât cheia sau lungimea a. dacă toate elementele din matrice sunt mai mici decât cheia specificată. Rețineți că acest lucru garantează că valoarea returnată va fi>= 0 dacă și numai dacă cheia este găsită.

Există anumite puncte importante de reținut, după cum urmează:

• Dacă lista de intrare nu este sortată, rezultatele sunt nedefinite.
• Dacă există duplicate, nu există nicio garanție care va fi găsit.

Ca mai sus, am discutat deja că putem opera acest algoritm Arrays.binarysearch() vs Collections.binarysearch() . Arrays.binarysearch() funcționează pentru tablouri care pot fi, de asemenea, de tipul de date primitiv. Colecții .binarysearch() funcționează pentru obiecte, cum ar fi colecții ArrayList și LinkedList .

Exemplul 1:

Java

butonul tkinter

>

>

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>

Analiza complexității:

Complexitatea timpului:
Complexitatea temporală a metodei Arrays.binarySearch() este O(log n) unde n este lungimea matricei de intrare. Acest lucru se datorează faptului că metoda folosește algoritmul de căutare binar pentru a găsi elementul țintă în matricea sortată.

Spațiu auxiliar:
Spațiul auxiliar folosit de metoda Arrays.binarySearch() este O(1), deoarece nu necesită spațiu suplimentar în afară de tabloul de intrare pentru a efectua operația de căutare.

listnode java

Există variante ale acestei metode în care putem specifica, de asemenea, intervalul de matrice în care să căutați. Vom discuta despre asta, precum și despre căutarea într-o matrice Object în postări ulterioare.

Exemplul 2:

Java

conversia unui șir în număr întreg

>

>

2>

Analiza complexității:

Complexitatea timpului:
Complexitatea de timp a metodei binarySearch() din clasa Collections este O(log n) unde n este numărul de elemente din listă.

Spațiu auxiliar:
Metoda binarySearch() din clasa Collections nu necesită spațiu suplimentar și, prin urmare, are o complexitate de spațiu auxiliar de O(1).