Een snelle methode om een bepaald element in een gesorteerde array te lokaliseren is een binaire zoekopdracht. De initiële taak van dit algoritme is het vergelijken van de doelwaarde met het middelste element van de array. De zoekopdracht wordt als succesvol beschouwd als de doelwaarde zich in het middelste element bevindt. Het algoritme kijkt in de linkerhelft van de array of de doelwaarde kleiner is dan het middelste element. Het programma scant de rechterhelft van de array als de doelwaarde groter is dan het middelste element. Deze methode wordt herhaald totdat de doelwaarde of het zoekbereik is uitgeput.
Gebruik:
Databases, zoekmachines en gegevensverwerking zijn slechts enkele van de toepassingen die de binaire zoekstrategie gebruiken.
Kenmerken:
- De array met invoerwaarden moet worden gesorteerd.
- Bij elke iteratie verkleint de methode het zoekbereik met de helft, waardoor deze bijzonder efficiënt is voor enorme datasets.
- Het algoritme heeft een O (log n) tijdscomplexiteit in het slechtste geval.
- Het vinden van de gewenste waarde gebeurt door het programma met behulp van een verdeel-en-heersstrategie.
Hier is een eenvoudig voorbeeld van het binaire zoekalgoritme geschreven in C:
#include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message 'Target not found' is displayed.</li> <li>The binary search algorithm's implementation is basic. We begin by setting the left border to the array's initial index and the right boundary to the array's last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index's floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique's overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=> - De binary_search-functie accepteert vier argumenten: de array waarin moet worden gezocht, de linker- en rechtergrenzen van het zoekbereik en de doelwaarde waarnaar moet worden gezocht. De functie retourneert zijn index als de gewenste waarde kan worden gevonden; anders retourneert het -1.
- De hoofdfunctie creëert een array arr en een waardedoel. De binary_search-functie wordt vervolgens gebruikt om in de array naar de gewenste waarde te zoeken. De functie retourneert de index waar de doelwaarde zich bevond, als deze zich bevond, retourneert de functie de index waarop deze werd gevonden. Anders wordt de melding 'Doel niet gevonden' weergegeven.
- De implementatie van het binaire zoekalgoritme is eenvoudig. We beginnen met het instellen van de linkergrens op de initiële index van de array en de rechtergrens op de laatste index van de array. Zodra de linkergrens kleiner is dan of gelijk is aan de rechtergrens, wordt de array nog een keer doorgelust. We gebruiken de formule (links + rechts) / 2 binnen de lus om de middelste index van het zoekbereik te berekenen. Deze formule berekent de gehele waarde van de bodem van de middelste index.
- Het middelste lid van de array staat in contrast met de doelwaarde. We retourneren de index van het middelste element als ze gelijk zijn. We veranderen de rechtergrens zodat deze één minder is dan de middelste index als de gewenste waarde kleiner is dan het middelste element. Als dat niet het geval is, passen we de linkerrand aan zodat deze één meer is dan de middelste index. Dit blijven we doen totdat de doelwaarde is behaald of de zoekruimte gevuld is.
- De temporele complexiteit van het binaire zoekalgoritme, waarbij n de arraygrootte is, is O(log n). Dit is veel efficiënter dan lineair zoeken, dat een temporele complexiteit heeft van O(n), waarbij n de grootte van de array is.
- Ten slotte biedt de binaire zoektechniek een handige manier om een bepaald lid in een gesorteerde array te lokaliseren. Het is eenvoudig te bouwen en heeft een O(log n) tijdcomplexiteit, waardoor het een efficiënte aanpak is voor grote datasets.
Voordelen:
- Voor grote datasets is het binaire zoekalgoritme uitzonderlijk efficiënt en kan het een breed scala aan invoergroottes verwerken.
- Het algoritme is eenvoudig te implementeren in vrijwel alle programmeertalen.
Nadelen:
- Voordat de binaire zoektechniek wordt gebruikt, moet de invoerarray worden gesorteerd, wat meer tijd en geheugen kost.
- Het algoritme kan niet worden toegepast op ongesorteerde arrays.
- Het algoritme kan onnauwkeurige resultaten opleveren als de invoerarray niet is gesorteerd.
- Het binaire zoekalgoritme is niet geschikt voor kleine datasets, omdat de overhead van de techniek mogelijk groter is dan de voordelen ervan.
Conclusie:
Een gesorteerde array kan snel worden doorzocht op een specifiek element met behulp van de binaire zoektechniek. Het maakt gebruik van een verdeel-en-heersstrategie om het zoekbereik bij elke iteratie te halveren, waardoor het zeer efficiënt kan zijn voor grote datasets. Voordat de binaire zoektechniek wordt gebruikt, moet de invoerarray echter worden gesorteerd, wat extra tijd en geheugen kost. Het binaire zoekalgoritme is een geavanceerd hulpmiddel voor gegevensverwerking dat op grote schaal wordt gebruikt in verschillende sectoren.