Arrays.binarySearch() metóda vyhľadá v zadanom poli daného dátového typu zadanú hodnotu pomocou binárneho vyhľadávacieho algoritmu. Pole musí byť zoradené podľa Arrays.sort() pred uskutočnením tohto hovoru. Ak nie je zoradené, výsledky sú nedefinované. Ak pole obsahuje viacero prvkov so zadanou hodnotou, nie je zaručené, ktorý z nich sa nájde. Prejdime si nižšie uvedený obrázok nasledovne.

Ilustrácia:

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>

Je to najjednoduchšia a najefektívnejšia metóda na nájdenie prvku v triedenom poli v jazyku Java

Syntax:

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

Pamätajte: Dátovým typom môže byť ktorýkoľvek z primitívnych dátových typov, ako napríklad byte, char, double, int, float, short, long a dokonca aj objekt.

Parametre:

• Pole, ktoré sa má prehľadávať
• Hodnota, ktorá sa má hľadať

Typ návratu: index vyhľadávacieho kľúča, ak je obsiahnutý v poli; inak (-(bod vloženia) – 1). Bod vloženia je definovaný ako bod, v ktorom by bol kľúč vložený do poľa: index prvého prvku väčší ako kľúč alebo a.length, ak sú všetky prvky v poli menšie ako zadaný kľúč. Všimnite si, že to zaručuje, že návratová hodnota bude>= 0 vtedy a len vtedy, ak sa nájde kľúč.

Je potrebné mať na pamäti nasledujúce dôležité body:

• Ak zoznam vstupov nie je zoradený, výsledky sú nedefinované.
• Ak existujú duplikáty, nie je zaručené, ktorý z nich sa nájde.

Ako je uvedené vyššie, už sme diskutovali o tom, že môžeme prevádzkovať aj tento algoritmus Arrays.binarysearch() vs Collections.binarysearch() . Arrays.binarysearch() funguje pre polia, ktoré môžu byť tiež primitívneho dátového typu. zbierky .binarysearch() funguje pre objekty ako kolekcie ArrayList a LinkedList .

Príklad 1:

Java

pre každý strojopis

>

>

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>

Analýza zložitosti:

Časová zložitosť:
Časová zložitosť metódy Arrays.binarySearch() je O(log n), kde n je dĺžka vstupného poľa. Je to preto, že metóda používa binárny vyhľadávací algoritmus na nájdenie cieľového prvku v triedenom poli.

Pomocný priestor:
Pomocný priestor používaný metódou Arrays.binarySearch() je O(1), pretože na vykonanie operácie vyhľadávania nevyžaduje žiadny ďalší priestor okrem vstupného poľa.

Existujú varianty tejto metódy, v ktorých môžeme špecifikovať aj rozsah poľa na vyhľadávanie. O tom, ako aj o vyhľadávaní v poli objektov, budeme diskutovať v ďalších príspevkoch.

Príklad 2:

vytlačiť vzor hviezdy

Java

rýchle triedenie java

>

>

2>

Analýza zložitosti:

Časová zložitosť:
Časová zložitosť metódy binarySearch() v triede Collections je O(log n), kde n je počet prvkov v zozname.

Pomocný priestor:
Metóda binarySearch() v triede Collections nevyžaduje žiadny priestor navyše, a preto má pomocnú priestorovú zložitosť O(1).