binary search algorithm java implementation examples
Ta vadnica bo razložila binarno iskanje in rekurzivno binarno iskanje v Javi skupaj s primeri algoritma, izvedbe in binarne kode iskanja Java:
Binarno iskanje v Javi je tehnika, ki se uporablja za iskanje ciljne vrednosti ali ključa v zbirki. Gre za tehniko, ki za iskanje ključa uporablja tehniko »deli in osvoji«.
Zbirko, za katero bo binarno iskanje uporabljeno za iskanje ključa, je treba razvrstiti po naraščajočem vrstnem redu.
Običajno večina programskih jezikov podpira tehnike linearnega iskanja, binarnega iskanja in razprševanja, ki se uporabljajo za iskanje podatkov v zbirki. V naslednjih vajah se bomo naučili razprševanja.
=> Obiščite tukaj, če se želite naučiti Jave iz nič.
Kaj se boste naučili:
Binarno iskanje v Javi
Linearno iskanje je osnovna tehnika. Pri tej tehniki se matrika prečka zaporedno in vsak element se primerja s ključem, dokler ključa ne najdejo ali konec matrike.
Linearno iskanje se redko uporablja v praktičnih aplikacijah. Binarno iskanje je najpogosteje uporabljena tehnika, saj je veliko hitrejše od linearnega iskanja.
Java ponuja tri načine za binarno iskanje:
vprašanja in odgovori za pogovore z informatiko powercenter
- Uporaba iterativnega pristopa
- Uporaba rekurzivnega pristopa
- Uporaba metode Arrays.binarySearch ().
V tej vadnici bomo izvedli in razpravljali o vseh treh metodah.
Algoritam za binarno iskanje v Javi
Pri metodi binarnega iskanja je zbirka večkrat razdeljena na polovico in ključni element se išče v levi ali desni polovici zbirke, odvisno od tega, ali je ključ manjši ali večji od srednjega elementa zbirke.
Preprost algoritem binarnega iskanja je naslednji:
- Izračunaj srednji element zbirke.
- Ključne elemente primerjajte s sredinskim elementom.
- Če je key = srednji element, vrnemo položaj srednjega indeksa za najdeni ključ.
- V nasprotnem primeru, če je tipka> srednji element, potem je ključ v desni polovici zbirke. Tako ponovite korake 1 do 3 na spodnji (desni) polovici zbirke.
- Drugače ključ
Kot lahko vidite iz zgornjih korakov, je pri binarnem iskanju polovica elementov v zbirki prezrta takoj po prvi primerjavi.
Upoštevajte, da velja enako zaporedje korakov za iterativno in rekurzivno binarno iskanje.
Na primeru ponazorimo algoritem binarnega iskanja.
Na primer, vzemite naslednjo razvrščeno polje z 10 elementi.
Izračunajmo srednjo lokacijo matrike.
Sredina = 0 + 9/2 = 4
orodje za preizkus spletne storitve za počitek
# 1) Ključ = 21
Najprej bomo primerjali vrednost ključa z elementom [mid] in ugotovili, da je vrednost elementa mid = 21.
Tako najdemo, da je ključ = [mid]. Zato se ključ nahaja na položaju 4 v matriki.
# 2) Ključ = 25
Najprej primerjamo ključno vrednost s srednjo vrednostjo. Kot (21<25), we will directly search for the key in the upper half of the array.
Zdaj bomo spet našli sredino za zgornjo polovico polja.
Sredina = 4 + 9/2 = 6
Vrednost na lokaciji [mid] = 25
Zdaj primerjamo ključni element s srednjim elementom. Torej (25 == 25), zato smo našli ključ na lokaciji [mid] = 6.
Tako matriko večkrat razdelimo in s primerjavo ključnega elementa s sredino odločimo, v kateri polovici bomo iskali ključ. Binarno iskanje je časovno in korektno bolj učinkovito in tudi veliko hitrejše.
Izvedba binarnega iskanja Java
Z uporabo zgornjega algoritma naj uporabimo program binarnega iskanja v Javi z uporabo iterativnega pristopa. V tem programu vzamemo primer matrike in na njej izvedemo binarno iskanje.
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!'); } } }
Izhod:
Vhodna matrika: [5, 10, 15, 20, 25, 30, 35]
Ključ za iskanje = 20
Element najdemo v indeksu: 3
Zgornji program prikazuje iterativni pristop binarnega iskanja. Sprva se navede matrika, nato se določi ključ, ki ga je treba iskati.
Po izračunu sredine polja se ključ primerja s sredinskim elementom. Nato ključ poiščemo v spodnji ali zgornji polovici polja, odvisno od tega, ali je tipka manjša ali večja od tipke.
Rekurzivno binarno iskanje v Javi
S tehniko rekurzije lahko izvedete tudi binarno iskanje. Tu se binarna metoda iskanja pokliče rekurzivno, dokler ključa ne najdemo ali celotnega seznama izčrpamo.
Program, ki izvaja rekurzivno binarno iskanje, je podan spodaj:
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'); } }
Izhod:
Seznam vnosov: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Ključ za iskanje:
Ključ najdete na mestu: 3 na seznamu
Uporaba metode Arrays.binarySearch ().
Razred Arrays v Javi ponuja metodo ‘binarySearch ()’, ki izvede binarno iskanje v danem polju. Ta metoda matriko in ključ išče kot argumente in vrne položaj ključa v matriki. Če ključa ne najdemo, potem metoda vrne -1.
Spodnji primer izvaja metodo 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.'); } }
Izhod:
Vhodno polje: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Ključ za iskanje: 50
Ključ se nahaja v indeksu: 4 v matriki.
Pogosto zastavljena vprašanja
V # 1) Kako napišem binarno iskanje?
Odgovor: Binarno iskanje se običajno izvede tako, da se matrika razdeli na polovice. Če je ključ, ki ga želite iskati, večji od srednjega elementa, potem zgornjo polovico matrike iščemo z nadaljnjim deljenjem in iskanjem podniz, dokler ne najdemo ključa.
Če je ključ manjši od srednjega elementa, se ključ išče v spodnji polovici polja.
V # 2) Kje se uporablja binarno iskanje?
Odgovor: Binarno iskanje se v glavnem uporablja za iskanje razvrščenih podatkov v programskih aplikacijah, zlasti kadar je pomnilniški prostor kompakten in omejen.
V # 3) Kaj je velik O binarnega iskanja?
posredujejo polje metodi java
Odgovor: Časovna zapletenost binarnega iskanja je O (logn), kjer je n število elementov v matriki. Prostorska zapletenost binarnega iskanja je O (1).
V # 4) Ali je binarno iskanje rekurzivno?
Odgovor: Da. Ker je binarno iskanje primer strategije »deli in vladaj« in ga je mogoče izvesti z uporabo rekurzije. Polje lahko razdelimo na polovice in pokličemo isto metodo, da znova in znova izvedemo binarno iskanje.
V # 5) Zakaj se imenuje binarno iskanje?
Odgovor: Binarni algoritem iskanja uporablja strategijo deli in vladaj, ki polje večkrat razreže na polovice ali dva dela. Tako se imenuje binarno iskanje.
Zaključek
Binarno iskanje je pogosto uporabljena tehnika iskanja v Javi. Zahteva za binarno iskanje je, da je treba podatke razvrstiti po naraščajočem vrstnem redu.
Binarno iskanje je mogoče izvesti bodisi z uporabo iterativnega ali rekurzivnega pristopa. Razred Arrays v Javi ponuja tudi metodo 'binarySearch', ki izvede binarno iskanje v matriki.
V naslednjih vajah bomo raziskali različne tehnike razvrščanja v Javi.
=> Tukaj si oglejte preproste vadbene serije Java.
Priporočeno branje
- Razvrščanje razvrščanja v Javi - Algoritem razvrščanja izbir in primeri
- Razvrstitev vstavitve v Javi - Algoritem razvrščanja vstavkov in primeri
- Binarno drevo iskanja C ++: Implementacija BST in operacije s primeri
- Vadnica Java vmesnika in abstraktnega razreda s primeri
- JAVA Vadnica za začetnike: 100+ praktičnih Javnih video vadnic
- Razvrstitev mehurčkov v Javi - algoritmi za razvrščanje Java in primeri kode
- Vadnica za Java String | Nizovske metode Java s primeri
- Kaj je Java Vector | Vadnica Java Vector Class s primeri