Menu

Algoritmus binárneho vyhľadávania v prostredí Java - implementácia a príklady

  • Hlavná
  • Iné
  • Algoritmus binárneho vyhľadávania v prostredí Java - implementácia a príklady

binary search algorithm java implementation examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento tutoriál vysvetlí binárne vyhľadávanie a rekurzívne binárne vyhľadávanie v prostredí Java spolu s príkladmi jeho algoritmu, implementácie a binárneho vyhľadávacieho kódu Java:

Binárne vyhľadávanie v prostredí Java je technika, ktorá sa používa na vyhľadávanie cieľovej hodnoty alebo kľúča v zbierke. Je to technika, ktorá využíva techniku ​​„rozdeľuj a panuj“ na hľadanie kľúča.

Zbierka, v ktorej sa má binárne vyhľadávanie použiť na hľadanie kľúča, je potrebné zoradiť vzostupne.

Väčšina programovacích jazykov zvyčajne podporuje techniky lineárneho, binárneho a hashovania, ktoré sa používajú na vyhľadávanie údajov v kolekcii. Hašovanie sa naučíme v našich ďalších tutoriáloch.

=> Navštívte tu a dozviete sa Java od začiatku.

Binárne vyhľadávanie v Jave

Čo sa dozviete:

Binárne vyhľadávanie v Jave

Lineárne vyhľadávanie je základná technika. V tejto technike sa po poli prechádza postupne a každý prvok sa porovnáva s kľúčom, kým sa nenájde kľúč alebo sa nedosiahne koniec poľa.

V praktických aplikáciách sa lineárne vyhľadávanie používa zriedka. Binárne vyhľadávanie je najčastejšie používanou technikou, pretože je oveľa rýchlejšie ako lineárne vyhľadávanie.

Java poskytuje tri spôsoby vykonávania binárneho vyhľadávania:

top 10 sťahovačov hudby pre Android
  1. Použitie iteračného prístupu
  2. Pomocou rekurzívneho prístupu
  3. Použitie metódy Arrays.binarySearch ().

V tomto tutoriále budeme implementovať a diskutovať o všetkých týchto 3 metódach.

Algoritmus pre binárne vyhľadávanie v prostredí Java

Pri metóde binárneho vyhľadávania je kolekcia opakovane rozdelená na polovicu a kľúčový prvok je prehľadávaný v ľavej alebo pravej polovici kolekcie podľa toho, či je kľúč menší alebo väčší ako stredný prvok kolekcie.

Jednoduchý binárny vyhľadávací algoritmus je nasledovný:

  1. Vypočítajte stredný prvok kolekcie.
  2. Porovnajte kľúčové položky so stredným prvkom.
  3. Ak kľúč = stredný prvok, potom vrátime strednú pozíciu indexu pre nájdený kľúč.
  4. Ak je kláves> stredný prvok, potom leží kláves v pravej polovici kolekcie. Opakujte teda kroky 1 až 3 v dolnej (pravej) polovici kolekcie.
  5. Inak kľúč

Ako môžete vidieť z vyššie uvedených krokov, v binárnom vyhľadávaní je polovica prvkov v kolekcii ignorovaná hneď po prvom porovnaní.

Upozorňujeme, že rovnaká postupnosť krokov platí pre iteratívne aj rekurzívne binárne vyhľadávanie.

Poďme si ilustrovať algoritmus binárneho vyhľadávania na príklade.

Napríklad, vezmite nasledujúce zoradené pole 10 prvkov.

Zoradené pole 10 prvkov

Poďme vypočítať stredné umiestnenie poľa.

Stred = 0 + 9/2 = 4

stredné umiestnenie poľa

# 1) Kľúč = 21

Najskôr porovnáme kľúčovú hodnotu s prvkom (mid) a zistíme, že hodnota prvku v strede = 21.

Kľúč = 21

Nájdeme teda tento kľúč = (stred). Preto sa kľúč nachádza na pozícii 4 v poli.

# 2) Kľúč = 25

Kľúč = 25

Najskôr porovnáme kľúčovú hodnotu so strednou. Ako (21<25), we will directly search for the key in the upper half of the array.

vyhľadajte kľúč v hornej polovici poľa.

Teraz opäť nájdeme stred pre hornú polovicu poľa.

Stred = 4 + 9/2 = 6

Hodnota na mieste (stred) = 25

hodnota v umiestnení (v strede) = 25

Teraz porovnáme kľúčový prvok so stredným prvkom. Takže (25 == 25), preto sme našli kľúč na mieste (v strede) = 6.

Takto opakovane rozdelíme pole a porovnaním kľúčového prvku so stredom sa rozhodneme, v ktorej polovici kľúč vyhľadáme. Binárne vyhľadávanie je efektívnejšie z hľadiska času a správnosti a je tiež oveľa rýchlejšie.

Implementácia binárneho vyhľadávania Java

Pomocou vyššie uvedeného algoritmu implementujme program binárneho vyhľadávania v Jave pomocou iteračného prístupu. V tomto programe si vezmeme príklad poľa a vykonáme binárne vyhľadávanie na tomto poli.

unixové otázky na pohovor s cieľom podpory výroby
import java.util.*; class Main{ public static void main(String args()){ int numArray() = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println(' Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray(mid) last ){ System.out.println('Element is not found!'); } } }

Výkon:

Vstupné pole: (5, 10, 15, 20, 25, 30, 35)
Kľúč, ktorý sa má vyhľadať = 20
Prvok sa nachádza v indexe: 3

Výstup - implementácia binárneho vyhľadávania v jave

Vyššie uvedený program ukazuje iteračný prístup binárneho vyhľadávania. Na začiatku je deklarované pole, potom je definovaný kľúč, ktorý sa má prehľadať.

Po vypočítaní stredu poľa sa kláves porovnáva so stredným prvkom. Potom v závislosti od toho, či je kľúč menší alebo väčší ako kľúč, sa kľúč vyhľadáva v dolnej alebo hornej polovici poľa.

Rekurzívne binárne vyhľadávanie v Jave

Môžete tiež vykonať binárne vyhľadávanie pomocou techniky rekurzie. Tu sa metóda binárneho vyhľadávania volá rekurzívne, kým sa nenájde kľúč alebo sa nevyčerpá celý zoznam.

Program, ktorý implementuje rekurzívne binárne vyhľadávanie, je uvedený nižšie:

import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray(), int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray(mid) return mid if (intArray(mid) == key){ return mid; } //if intArray(mid) > key then key is in left half of array if (intArray(mid) > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args()){ //define array and key int intArray() = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println(' The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println(' Key not found in given list!'); else System.out.println(' Key is found at location: '+result + ' in the list'); } }

Výkon:

Zoznam vstupov: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Kľúč, ktorý sa má vyhľadať:
Kľúč sa nachádza v zozname na mieste 3

Výstup - rekurzívne binárne vyhľadávanie v Jave

Použitie metódy Arrays.binarySearch ().

Trieda Arrays v Jave poskytuje metódu ‘binarySearch ()’, ktorá vykonáva binárne vyhľadávanie na danom poli. Táto metóda vezme pole a kľúč, ktorý sa má vyhľadať, ako argumenty a vráti pozíciu kľúča v poli. Ak sa kľúč nenájde, metóda vráti -1.

Nasledujúci príklad implementuje metódu Arrays.binarySearch ().

import java.util.Arrays; class Main{ public static void main(String args()){ //define an array int intArray() = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println(' The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println(' Key is not found in the array!'); else System.out.println(' Key is found at index: '+result + ' in the array.'); } }

Výkon:

Vstupné pole: (10, 20, 30, 40, 50, 60, 70, 80, 90)
Kľúč, ktorý sa má vyhľadať: 50
Kľúč sa nachádza v indexe: 4 v poli.

Výstup - použitie metódy Arrays.binarySearch ().

často kladené otázky

Otázka 1) Ako napíšete binárne vyhľadávanie?

Odpoveď: Binárne vyhľadávanie sa zvyčajne vykonáva rozdelením poľa na polovice. Ak je kľúč, ktorý sa má prehľadať, väčší ako stredný prvok, potom sa prehľadá horná polovica poľa ďalším delením a prehľadávaním čiastkového poľa, kým sa nenájde kľúč.

Podobne, ak je kľúč menší ako stredný prvok, potom sa kľúč hľadá v dolnej polovici poľa.

Otázka 2) Kde sa používa binárne vyhľadávanie?

Odpoveď: Binárne vyhľadávanie sa používa hlavne na vyhľadávanie zoradených údajov v softvérových aplikáciách, najmä ak je pamäťový priestor kompaktný a obmedzený.

Otázka č. 3) Čo je veľké O binárneho vyhľadávania?

Odpoveď: Časová zložitosť binárneho vyhľadávania je O (logn), kde n je počet prvkov v poli. Komplexnosť priestoru binárneho vyhľadávania je O (1).

Otázka č. 4) Je binárne vyhľadávanie rekurzívne?

Odpoveď: Áno. Pretože binárne vyhľadávanie je príkladom stratégie rozdelenia a dobývania a dá sa implementovať pomocou rekurzie. Môžeme rozdeliť pole na polovice a zavolať tú istú metódu na vykonávanie binárneho vyhľadávania znova a znova.

Otázka č. 5) Prečo sa to nazýva binárne vyhľadávanie?

Odpoveď: Algoritmus binárneho vyhľadávania používa stratégiu rozdeľuj a panuj, ktorá opakovane rozdeľuje pole na polovice alebo na dve časti. Preto je pomenovaný ako binárne vyhľadávanie.

Záver

Binárne vyhľadávanie je často používanou technikou vyhľadávania v Jave. Požiadavkou na vykonanie binárneho vyhľadávania je, aby boli údaje zoradené vzostupne.

Binárne vyhľadávanie je možné implementovať pomocou iteratívneho alebo rekurzívneho prístupu. Trieda Arrays v Jave tiež poskytuje metódu „binarySearch“, ktorá vykonáva binárne vyhľadávanie na poli.

char na celé číslo c ++

V našich ďalších tutoriáloch preskúmame rôzne techniky triedenia v Jave.

=> Dajte si pozor na jednoduchú sériu školení Java tu.

Odporúčané čítanie

^