Binarni algoritam pretraživanja na Javi

1. Pregled

U ovom ćemo članku pokriti prednosti binarnog pretraživanja u odnosu na jednostavno linearno pretraživanje i proći ćemo kroz njegovu implementaciju u Javi.

2. Potreba za učinkovitom pretragom

Recimo da se bavimo prodajom vina i milijuni kupaca svakodnevno posjećuju našu aplikaciju.

Kroz našu aplikaciju kupac može filtrirati stavke čija je cijena niža n dolara, odaberite bocu iz rezultata pretraživanja i dodajte ih u svoju košaricu. Milijuni korisnika svake sekunde traže vina s ograničenjem cijene. Rezultati moraju biti brzi.

Na pozadini, naš algoritam pokreće linearno pretraživanje cijelog popisa vina uspoređujući ograničenje cijene koje je kupac unijeo u cijenu svake boce vina s popisa.

Zatim vraća stavke čija je cijena manja ili jednaka ograničenju cijene. Ova linearna pretraga vremenski je složena Na).

To znači da što je veći broj boca vina u našem sustavu, to će vam trebati više vremena. Vrijeme pretraživanja povećava se proporcionalno broju novih stavki.

Ako započnemo spremati stavke u razvrstanom redoslijedu i tražimo stavke pomoću binarnog pretraživanja, možemo postići složenost O (zapisnik n).

Kod binarnog pretraživanja, vrijeme potrebno rezultatima pretraživanja prirodno se povećava s veličinom skupa podataka, ali ne proporcionalno.

3. Binarno pretraživanje

Jednostavno rečeno, algoritam uspoređuje ključ vrijednost sa srednjim elementom niza; ako su nejednaki, eliminira se polovica u kojoj ključ ne može biti dio, a potraga se nastavlja za preostalom polovicom dok ne uspije.

Zapamtite - ključni aspekt ovdje je taj što je niz već sortiran.

Ako pretraga završi praznom preostalom polovicom, ključ nije u polju.

3.1. Iterativne impl

javni int runBinarySearchIteratively (int [] sortedArray, int ključ, int nizak, int visok) {int indeks = Integer.MAX_VALUE; dok je (nisko <= visoko) {int srednje = (nisko + visoko) / 2; if (tipka sortedArray [mid]) {visoka = sredina - 1; } else if (sortedArray [mid] == key) {index = mid; pauza; }} indeks povrata; }

The runBinarySearchIteratively metoda traje a sortedArray, ključ & the niska & visoko indeksi sortedArray kao argumenti. Kada se metoda prvi put pokrene, niska, prvi indeks sortedArray, je 0, dok je visoko, posljednji indeks sortedArray, jednaka je njegovoj duljini - 1.

The srednji je srednji indeks sortedArray. Sada algoritam pokreće a dok petlja uspoređujući ključ s vrijednošću niza srednjeg indeksa sortedArray.

3.2. Rekurzivni Impl

Pogledajmo sada i jednostavnu, rekurzivnu implementaciju:

javni int runBinarySearchRecursively (int [] sortedArray, int ključ, int nizak, int visok) {int srednji = (niski + visoki) / 2; ako (visoko <nisko) {povratak -1; } if (ključ == sortedArray [sredina]) {return sredina; } else if (ključ <sortedArray [sredina]) {return runBinarySearchRecursively (sortedArray, ključ, niska, sredina - 1); } else {povratak runBinarySearchRecursively (sortedArray, key, middle + 1, high); }} 

The runBinarySearchRecursively metoda prihvaća a sortedArray, ključ, the niska i visoko indeksi sortedArray.

3.3. Koristeći Nizovi.binarySearch ()

int index = Arrays.binarySearch (sortedArray, ključ); 

SortiraniArray i an intključ, koji treba pretražiti u nizu cijelih brojeva, predaju se kao argumenti datoteci binarySearch metoda Java Nizovi razred.

3.4. Koristeći Zbirke.binarySearch ()

int index = Collections.binarySearch (sortedList, key); 

Poredana lista & an Cijeli brojključ, koji se traži na popisu Cijeli broj objekti, prosljeđuju se kao argumenti datoteci binarySearch metoda Java Zbirke razred.

3.5. Izvođenje

Hoće li se za pisanje algoritma koristiti rekurzivni ili iterativni pristup uglavnom je stvar osobnih preferencija. No, ipak postoji nekoliko točaka kojih bismo trebali biti svjesni:

1. Rekurzija može biti sporija zbog režijskih troškova održavanja a stog i obično zauzima više memorije

2. Rekurzija nije stog-prijateljski. Može uzrokovati StackOverflowException prilikom obrade skupova velikih podataka

3. Rekurzija dodaje jasnoću kodu jer ga čini kraćim u usporedbi s iterativnim pristupom

U idealnom slučaju, binarno pretraživanje izvest će manji broj usporedbi za razliku od linearnog pretraživanja velikih vrijednosti n. Za manje vrijednosti n, linearno bi pretraživanje moglo biti bolje od binarnog pretraživanja.

Treba znati da je ova analiza teoretska i da se može razlikovati ovisno o kontekstu.

Također, algoritam binarnog pretraživanja treba razvrstani skup podataka koji ima i svoje troškove. Ako za sortiranje podataka koristimo algoritam sortiranja spajanja, dodatna složenost n log n je dodan našem kodu.

Dakle, prvo moramo dobro analizirati svoje zahtjeve, a zatim donijeti odluku koji algoritam pretraživanja najbolje odgovara našim zahtjevima.

4. Zaključak

Ovaj je vodič pokazao implementaciju binarnog algoritma pretraživanja i scenarij u kojem bi bilo poželjnije koristiti ga umjesto linearnog pretraživanja.

Kôd vodiča potražite na GitHubu.