streamalism.org

1. Oversikt

I denne artikkelen vil vi dekke fordelene med et binært søk fremfor et enkelt lineært søk og gå gjennom implementeringen av den i Java.

2. Behov for effektiv søk

La oss si at vi er i vinsalgssektoren og millioner av kjøpere besøker applikasjonen vår hver dag.

Gjennom appen vår kan en kunde filtrere ut varer som har en pris nedenfor n dollar, velg en flaske fra søkeresultatene, og legg dem i handlekurven. Vi har millioner av brukere som søker viner med en prisgrense hvert sekund. Resultatene må være raske.

På baksiden kjører algoritmen vår et lineært søk gjennom hele listen over viner som sammenligner prisgrensen som kunden har oppgitt med prisen på hver vinflaske i listen.

Deretter returnerer den varer som har en pris som er mindre enn eller lik prisgrensen. Dette lineære søket har en tidskompleksitet på På).

Dette betyr at jo større antall vinflasker i systemet vårt, jo mer tid vil det ta. Søketiden øker proporsjonalt med antall nye artikler som er introdusert.

Hvis vi begynner å lagre varer i sortert rekkefølge og søke etter varer ved hjelp av binært søk, kan vi oppnå en kompleksitet på O (log n).

Med binært søk øker naturligvis søkeresultatene med datasettets størrelse, men ikke proporsjonalt.

3. Binært søk

Enkelt sagt, algoritmen sammenligner nøkkel verdi med det midterste elementet i matrisen; hvis de ikke er like, blir den halve nøkkelen ikke kan være en del av, eliminert, og søket fortsetter etter den gjenværende halvdelen til den lykkes.

Husk - nøkkelaspektet her er at matrisen allerede er sortert.

Hvis søket ender med at den resterende halvdelen er tom, blir nøkkel er ikke i matrisen.

3.1. Iterativ Impl

public int runBinarySearchIteratively (int [] sortedArray, int key, int low, int high) {int index = Integer.MAX_VALUE; mens (lav <= høy) {int midt = (lav + høy) / 2; if (sortedArray [mid] key) {high = mid - 1; } annet hvis (sortedArray [mid] == nøkkel) {index = mid; gå i stykker; }} returindeks; }

De runBinarySearchIterativt metoden tar en sortedArray, nøkkel & lav & høy indekser av sortedArray som argumenter. Når metoden kjører for første gang lav, den første indeksen av sortertArray, er 0, mens høy, den siste indeksen av sortertArray, er lik lengden - 1.

De midten er midtindeksen til sortedArray. Nå kjører algoritmen en samtidig som løkke som sammenligner nøkkel med matriseverdien til den midterste indeksen til sortedArray.

3.2. Rekursivt impl

La oss nå se på en enkel, rekursiv implementering også:

public int runBinarySearchRecursively (int [] sortedArray, int key, int low, int high) {int middle = (low + high) / 2; hvis (høy <lav) {retur -1; } hvis (nøkkel == sortedArray [midt]) {retur midt; } annet hvis (nøkkel <sortedArray [midten]) {retur runBinarySearchRecursively (sortedArray, nøkkel, lav, midt - 1); } annet {return runBinarySearchRecursively (sortedArray, key, middle + 1, high); }} 

De runBinarySearchRecursively metoden godtar en sortedArray, nøkkel, de lav og høy indekser av sortedArray.

3.3. Ved hjelp av Arrays.binærsøk ()

int index = Arrays.binarySearch (sortedArray, key); 

En sortert Array og en intnøkkel, som skal søkes i en rekke med heltall, sendes som argumenter til binærsøk metoden til Java Arrays klasse.

3.4. Ved hjelp av Samlinger.binærsøk ()

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

En sortert liste & en Heltallnøkkel, som skal søkes i listen over Heltall objekter, blir sendt som argumenter til binærsøk metoden til Java Samlinger klasse.

3.5. Opptreden

Hvorvidt du skal bruke en rekursiv eller en iterativ tilnærming for å skrive algoritmen, er for det meste et spørsmål om personlig preferanse. Men fremdeles er det noen få punkter vi bør være klar over:

1. Rekursjon kan gå tregere på grunn av overhead for å opprettholde en stable og tar vanligvis mer minne

2. Rekursjon er ikke det stable-vennlig. Det kan forårsake StackOverflowException når du behandler store datasett

3. Rekursjon gir koden klarhet da den gjør den kortere i forhold til den iterative tilnærmingen

Ideelt sett vil et binært søk utføre mindre antall sammenligninger i motsetning til et lineært søk etter store verdier på n. For mindre verdier av n, kan det lineære søket fungere bedre enn et binært søk.

Man bør vite at denne analysen er teoretisk og kan variere avhengig av konteksten.

Også, den binære søkealgoritmen trenger et sortert datasett som også har sine kostnader. Hvis vi bruker en flettesorteringsalgoritme for å sortere dataene, er en ekstra kompleksitet på n log n er lagt til koden vår.

Så først må vi analysere kravene våre godt og deretter ta en beslutning om hvilken søkealgoritme som passer best til våre krav.

4. Konklusjon

Denne opplæringen demonstrerte en implementering av binær søkealgoritme og et scenario der det ville være å foretrekke å bruke den i stedet for et lineært søk.

Vennligst finn koden for opplæringen over på GitHub.