Binär sökalgoritm i Java

1. Översikt

I den här artikeln kommer vi att täcka fördelarna med en binär sökning jämfört med en enkel linjär sökning och gå igenom dess implementering i Java.

2. Behov av effektiv sökning

Låt oss säga att vi är i vinförsäljningsbranschen och miljontals köpare besöker vår applikation varje dag.

Genom vår app kan en kund filtrera bort varor som har ett pris under n dollar, välja en flaska från sökresultaten och lägga till dem i sin kundvagn. Vi har miljontals användare som söker viner med en prisgräns varje sekund. Resultaten måste vara snabba.

På backend kör vår algoritm en linjär sökning genom hela listan över viner som jämför prisgränsen som kunden har angett med priset på varje vinflaska i listan.

Sedan returnerar den varor som har ett pris som är lägre än eller lika med prisgränsen. Denna linjära sökning har en tidskomplexitet av O (n) .

Detta innebär att ju större antal vinflaskor i vårt system, desto mer tid tar det. Söktiden ökar proportionellt med antalet nya artiklar som introducerats.

Om vi ​​börjar spara objekt i sorterad ordning och söka efter objekt med binär sökning kan vi uppnå en komplexitet av O (log n) .

Med binär sökning ökar naturligtvis den tid det tar av sökresultaten med storleken på datasetet, men inte proportionellt.

3. Binär sökning

Enkelt uttryckt jämför algoritmen nyckelvärdet med mittelementet i matrisen; om de är ojämna elimineras den halva som nyckeln inte kan ingå i, och sökningen fortsätter efter den återstående hälften tills den lyckas.

Kom ihåg - nyckelaspekten här är att matrisen redan är sorterad.

Om sökningen slutar med att den återstående halvan är tom finns inte nyckeln i matrisen.

3.1. Iterativt Impl

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

Den runBinarySearchIteratively metod tar en sortedArray , nyckel & den låga & höga index av sortedArray som argument. När metoden körs för första gången är low , det första indexet för sortedArray 0, medan det höga , det sista indexet för sortedArray, är lika med dess längd - 1.

Den mellersta är mitt index för sortedArray . Nu algoritmen körs en stund slinga som jämför nyckeln med arrayen värdet av den mellersta index hos sortedArray .

3.2. Rekursivt Impl

Nu ska vi också titta på ett enkelt, rekursivt genomförande:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

Den runBinarySearchRecursively metoden accepterar en sortedArray , nyckel, den låga och höga index av sortedArray .

3.3. Använda arrays. binärsökning ()

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

En sortedArray och en int- nyckel , som ska sökas i arrayen av heltal, skickas som argument till binärsökningsmetoden i klassen Java Arrays .

3.4. Använda samlingar. binärsökning ()

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

En sortedList och en Integer- nyckel , som ska sökas i listan över Integer- objekt, skickas som argument till binärsökningsmetoden i Java Collections- klassen.

3.5. Prestanda

Huruvida man ska använda en rekursiv eller iterativ metod för att skriva algoritmen är mest en fråga om personlig preferens. Men här är fortfarande några punkter som vi bör vara medvetna om:

1. Rekursion kan vara långsammare på grund av att det kostar att bibehålla en stack och tar vanligtvis mer minne

2. Rekursion är inte stackvänlig . Det kan orsaka StackOverflowException vid bearbetning av stora datamängder

3. Rekursion ger koden tydligare eftersom den gör den kortare jämfört med den iterativa metoden

Helst kommer en binär sökning att utföra mindre antal jämförelser i motsats till en linjär sökning efter stora värden på n. För mindre värden på n kan linjär sökning fungera bättre än en binär sökning.

Man bör veta att denna analys är teoretisk och kan variera beroende på sammanhanget.

Den binära sökalgoritmen behöver också en sorterad datamängd som också har sina kostnader . Om vi ​​använder en sammanslagningsalgoritm för att sortera data läggs ytterligare en komplexitet på n log n till vår kod.

Så först måste vi analysera våra krav väl och sedan fatta ett beslut om vilken sökalgoritm som bäst passar våra krav.

4. Slutsats

Denna handledning visade en implementering av binär sökalgoritm och ett scenario där det skulle vara bättre att använda den istället för en linjär sökning.

Vänligen hitta koden för självstudien på GitHub.