streamalism.org

1. Oversigt

I denne artikel dækker vi fordelene ved en binær søgning frem for en simpel lineær søgning og gennemgår dens implementering i Java.

2. Behov for effektiv søgning

Lad os sige, at vi arbejder inden for vinsalg, og millioner af købere besøger vores applikation hver dag.

Via vores app kan en kunde filtrere varer, der har en pris nedenfor n dollars, vælg en flaske fra søgeresultaterne, og tilføj dem til hans indkøbskurv. Vi har millioner af brugere, der søger vine med en prisbegrænsning hvert sekund. Resultaterne skal være hurtige.

På backend kører vores algoritme en lineær søgning gennem hele listen over vine, der sammenligner den prisgrænse, der er indtastet af kunden, med prisen på hver vinflaske på listen.

Derefter returnerer den varer, der har en pris, der er mindre end eller lig med prisgrænsen. Denne lineære søgning har en tidskompleksitet på På).

Dette betyder, at jo større antallet af vinflasker i vores system, jo ​​mere tid tager det. Søgetiden øges forholdsmæssigt med antallet af nye varer, der introduceres.

Hvis vi begynder at gemme varer i sorteret rækkefølge og søge efter varer ved hjælp af binær søgning, kan vi opnå en kompleksitet på O (log n).

Med binær søgning øges den tid, som søgeresultaterne tager, naturligvis med datasættets størrelse, men ikke forholdsmæssigt.

3. Binær søgning

Kort sagt, algoritmen sammenligner nøgle værdi med det midterste element i arrayet; hvis de er ulige, elimineres den halvdel, som nøglen ikke kan være en del af, og søgningen fortsætter efter den resterende halvdel, indtil den lykkes.

Husk - nøgleaspektet her er, at arrayet allerede er sorteret.

Hvis søgningen slutter med den resterende halvdel tom, vises nøgle er ikke i matrixen.

3.1. Iterativ Impl

public int runBinarySearchIteratively (int [] sortedArray, int key, int low, int high) {int index = Integer.MAX_VALUE; mens (lav <= høj) {int midt = (lav + høj) / 2; hvis (sortedArray [mid] nøgle) {high = mid - 1; } ellers hvis (sortedArray [mid] == nøgle) {index = mid; pause; }} returindeks; }

Det runBinarySearchIterativt metoden tager en sorteretArray, nøgle & det lav & høj indekser af sorteretArray som argumenter. Når metoden kører for første gang, lav, det første indeks for sorteretArray, er 0, mens høj, det sidste indeks for sorteretArray, er lig med længden - 1.

Det midt er det midterste indeks for sorteretArray. Nu kører algoritmen en mens loop, der sammenligner nøgle med matrixværdien af ​​det midterste indeks for sorteretArray.

3.2. Rekursivt impl

Lad os nu også se på en enkel, rekursiv implementering:

public int runBinarySearchRecursively (int [] sortedArray, int key, int low, int high) {int middle = (low + high) / 2; hvis (høj <lav) {retur -1; } if (key == sortedArray [middle]) {return middle; } ellers hvis (nøgle <sortedArray [middle]) {return runBinarySearchRecursively (sortedArray, key, low, middle - 1); } andet {return runBinarySearchRecursively (sortedArray, key, middle + 1, high); }} 

Det runBinarySearchRecursively metode accepterer en sorteretArray, nøgle, det lav og høj indekser af sorteretArray.

3.3. Ved brug af Arrays.binærsøgning ()

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

En sorteret Array og en intnøgle, der skal søges i arrayet af heltal, sendes som argumenter til binærsøgning metode til Java Arrays klasse.

3.4. Ved brug af Samlinger.binærsøgning ()

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

En sorteret liste & en Heltalnøgle, der skal søges i listen over Heltal objekter, sendes som argumenter til binærsøgning metode til Java Samlinger klasse.

3.5. Ydeevne

Om man skal bruge en rekursiv eller en iterativ tilgang til at skrive algoritmen er mest et spørgsmål om personlig præference. Men stadig her er et par punkter, som vi bør være opmærksomme på:

1. Rekursion kan være langsommere på grund af omkostningerne ved at opretholde en stak og tager normalt mere hukommelse

2. Rekursion er ikke stak-venlige. Det kan forårsage StackOverflowException ved behandling af store datasæt

3. Rekursion tilføjer koden klarhed, da den gør den kortere sammenlignet med den iterative tilgang

Ideelt set udfører en binær søgning mindre antal sammenligninger i modsætning til en lineær søgning efter store værdier på n. For mindre værdier på n kunne den lineære søgning fungere bedre end en binær søgning.

Man skal vide, at denne analyse er teoretisk og kan variere afhængigt af sammenhængen.

Også, den binære søgealgoritme har brug for et sorteret datasæt, som også har sine omkostninger. Hvis vi bruger en flettesorteringsalgoritme til sortering af data, er en yderligere kompleksitet på n log n føjes til vores kode.

Så først skal vi analysere vores krav godt og derefter tage en beslutning om, hvilken søgealgoritme der passer bedst til vores krav.

4. Konklusion

Denne vejledning demonstrerede en implementering af binær søgealgoritme og et scenarie, hvor det ville være at foretrække at bruge den i stedet for en lineær søgning.

Find koden til vejledningen over på GitHub.