streamalism.org

1. Overzicht

In dit artikel bespreken we de voordelen van een binaire zoekopdracht ten opzichte van een eenvoudige lineaire zoekopdracht en bespreken we de implementatie ervan in Java.

2. Behoefte aan efficiënt zoeken

Laten we zeggen dat we in de wijnverkoop zijn en dat miljoenen kopers onze applicatie elke dag bezoeken.

Via onze app kan een klant items uitfilteren die een lagere prijs hebben n dollars, selecteer een fles uit de zoekresultaten en voeg ze toe aan zijn winkelwagentje. We hebben miljoenen gebruikers die op zoek zijn naar wijnen met elke seconde een prijslimiet. De resultaten moeten snel zijn.

Aan de achterkant voert ons algoritme een lineaire zoekopdracht uit door de volledige wijnlijst, waarbij de door de klant ingevoerde prijslimiet wordt vergeleken met de prijs van elke wijnfles in de lijst.

Vervolgens worden items geretourneerd die een prijs hebben die lager is dan of gelijk is aan de prijslimiet. Deze lineaire zoekopdracht heeft een tijdcomplexiteit van Aan).

Dit betekent dat hoe groter het aantal wijnflessen in ons systeem, hoe meer tijd het kost. De zoektijd neemt evenredig toe met het aantal nieuwe items dat wordt geïntroduceerd.

Als we items in gesorteerde volgorde gaan opslaan en naar items zoeken met behulp van de binaire zoekopdracht, kunnen we een complexiteit bereiken van O (logboek n).

Bij binair zoeken neemt de tijd die de zoekresultaten in beslag nemen natuurlijk toe met de grootte van de dataset, maar niet proportioneel.

3. Binair zoeken

Simpel gezegd, het algoritme vergelijkt de sleutel waarde met het middelste element van de array; als ze ongelijk zijn, wordt de helft waarin de sleutel geen deel kan uitmaken, geëlimineerd en gaat het zoeken door naar de resterende helft totdat het lukt.

Onthoud - het belangrijkste aspect hier is dat de array al is gesorteerd.

Als de zoekopdracht eindigt terwijl de resterende helft leeg is, wordt de sleutel staat niet in de array.

3.1. Iteratief geïmpl

openbare int runBinarySearchIterively (int [] gesorteerdArray, int sleutel, int laag, int hoog) {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; breken; }} retourneer index; }

De runBinarySearchIterative methode duurt een gesorteerdArray, sleutel & de laag & hoog indexen van de gesorteerdArray als argumenten. Wanneer de methode voor de eerste keer wordt uitgevoerd, wordt het laag, de eerste index van de gesorteerdArray, is 0, terwijl de hoog, de laatste index van de gesorteerdArray, is gelijk aan de lengte - 1.

De midden- is de middelste index van de gesorteerdArray. Nu voert het algoritme een terwijl lus die de sleutel met de matrixwaarde van de middelste index van de gesorteerdArray.

3.2. Recursieve Impl

Laten we nu eens kijken naar een eenvoudige, recursieve implementatie:

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

De runBinarySearchRecursively methode accepteert een gesorteerdArray, sleutel, de laag en hoog indexen van de gesorteerdArray.

3.3. Gebruik makend van Arrays.Binaire zoekopdracht()

int index = Arrays.binarySearch (gesorteerdArray, sleutel); 

Een gesorteerde Array en een intsleutel, die moet worden doorzocht in de array met gehele getallen, worden als argumenten doorgegeven aan de Binaire zoekopdracht methode van de Java Arrays klasse.

3.4. Gebruik makend van Collecties.Binaire zoekopdracht()

int index = Collections.binarySearch (gesorteerde lijst, sleutel); 

Een gesorteerde lijst & een Geheel getalsleutel, die moet worden doorzocht in de lijst met Geheel getal objecten, worden als argumenten doorgegeven aan de Binaire zoekopdracht methode van de Java Collecties klasse.

3.5. Prestatie

Of u een recursieve of een iteratieve benadering wilt gebruiken voor het schrijven van het algoritme, is meestal een kwestie van persoonlijke voorkeur. Maar toch zijn hier een paar punten waar we op moeten letten:

1. Recursie kan langzamer zijn vanwege de overhead van het onderhouden van een stapel en neemt meestal meer geheugen in beslag

2. Recursie is dat niet stapel-vriendelijk. Het kan leiden tot StackOverflowException bij het verwerken van big data sets

3. Recursie voegt duidelijkheid toe aan de code omdat het deze korter maakt in vergelijking met de iteratieve benadering

Idealiter zal een binaire zoekopdracht minder vergelijkingen opleveren in tegenstelling tot een lineaire zoekopdracht naar grote waarden van n. Voor kleinere waarden van n zou de lineaire zoekopdracht beter kunnen presteren dan een binaire zoekopdracht.

Men moet weten dat deze analyse theoretisch is en kan variëren afhankelijk van de context.

Ook, het binaire zoekalgoritme heeft een gesorteerde dataset nodig die ook zijn kosten met zich meebrengt. Als we een samenvoegsorteeralgoritme gebruiken voor het sorteren van de gegevens, ontstaat een extra complexiteit van n log n is toegevoegd aan onze code.

Dus eerst moeten we onze vereisten goed analyseren en dan een beslissing nemen welk zoekalgoritme het beste bij onze vereisten past.

4. Conclusie

Deze tutorial demonstreerde een implementatie van een binair zoekalgoritme en een scenario waarin het beter zou zijn om het te gebruiken in plaats van een lineaire zoekactie.

Vind de code voor de tutorial op GitHub.