Eine schnelle Methode zum Auffinden eines bestimmten Elements in einem sortierten Array ist eine binäre Suche. Die erste Aufgabe dieses Algorithmus besteht darin, den Zielwert mit dem mittleren Element des Arrays zu vergleichen. Die Suche gilt als erfolgreich, wenn der Zielwert im mittleren Element enthalten ist. Der Algorithmus sucht in der linken Hälfte des Arrays, wenn der Zielwert kleiner als das mittlere Element ist. Das Programm scannt die rechte Hälfte des Arrays, wenn der Zielwert größer als das mittlere Element ist. Diese Methode wird wiederholt, bis entweder der Zielwert oder der Suchbereich erschöpft ist.
Verwendung:
Datenbanken, Suchmaschinen und Datenverarbeitung sind nur einige der Anwendungen, die die binäre Suchstrategie nutzen.
Eigenschaften:
- Das Array der Eingabewerte muss sortiert sein.
- Mit jeder Iteration verkleinert die Methode den Suchbereich um die Hälfte, was sie besonders effizient für große Datensätze macht.
- Der Algorithmus hat im ungünstigsten Fall eine Zeitkomplexität von O (log n).
- Das Finden des gewünschten Werts erfolgt durch das Programm mithilfe einer Teile-und-Herrsche-Strategie.
Hier ist ein einfaches Beispiel für den in C geschriebenen binären Suchalgorithmus:
#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></=> - Die Funktion „binary_search“ akzeptiert vier Argumente: das zu durchsuchende Array, die linken und rechten Suchbereichsgrenzen und den zu suchenden Zielwert. Die Funktion gibt ihren Index zurück, wenn der gewünschte Wert gefunden werden kann; andernfalls wird -1 zurückgegeben.
- Die Hauptfunktion erstellt ein Array arr und ein Wertziel. Anschließend wird mit der Funktion „binary_search“ das Array nach dem gewünschten Wert durchsucht. Die Funktion gibt den Index zurück, an dem sich der Zielwert befand. Wenn dies der Fall war, gibt die Funktion den Index zurück, an dem er gefunden wurde. Andernfalls wird die Meldung „Ziel nicht gefunden“ angezeigt.
- Die Implementierung des binären Suchalgorithmus ist einfach. Wir beginnen damit, dass wir den linken Rand auf den Anfangsindex des Arrays und den rechten Rand auf den letzten Index des Arrays setzen. Sobald die linke Grenze kleiner oder gleich der rechten Grenze ist, wird das Array noch einmal durchlaufen. Wir verwenden die Formel (links + rechts) / 2 innerhalb der Schleife, um den mittleren Index des Suchbereichs zu berechnen. Diese Formel berechnet den ganzzahligen Wert der Untergrenze des mittleren Index.
- Das mittlere Element des Arrays wird dem Zielwert gegenübergestellt. Wir geben den Index des mittleren Elements zurück, wenn sie gleich sind. Wir ändern die rechte Grenze so, dass sie um eins kleiner als der mittlere Index ist, wenn der gewünschte Wert kleiner als das mittlere Element ist. Wenn nicht, passen wir den linken Rand so an, dass er um eins größer ist als der mittlere Index. Wir machen so lange weiter, bis der Zielwert erreicht ist oder der Suchraum gefüllt ist.
- Die zeitliche Komplexität des binären Suchalgorithmus, wobei n die Array-Größe ist, beträgt O(log n). Dies ist weitaus effizienter als die lineare Suche, die eine zeitliche Komplexität von O(n) aufweist, wobei n die Größe des Arrays ist.
- Schließlich bietet die binäre Suchtechnik eine nützliche Möglichkeit, ein bestimmtes Mitglied in einem sortierten Array zu finden. Es ist einfach zu erstellen und weist eine Zeitkomplexität von O(log n) auf, was es zu einem effizienten Ansatz für große Datenmengen macht.
Vorteile:
- Bei großen Datensätzen ist der binäre Suchalgorithmus außerordentlich effizient und kann ein breites Spektrum an Eingabegrößen verarbeiten.
- Der Algorithmus ist in fast allen Programmiersprachen einfach zu implementieren.
Nachteile:
- Vor der Verwendung der binären Suchtechnik muss das Eingabearray sortiert werden, was mehr Zeit und Speicher beansprucht.
- Der Algorithmus kann nicht auf unsortierte Arrays angewendet werden.
- Der Algorithmus kann zu ungenauen Ergebnissen führen, wenn das Eingabearray nicht sortiert ist.
- Der binäre Suchalgorithmus eignet sich nicht für kleine Datensätze, da der Aufwand der Technik ihre Vorteile überwiegen kann.
Abschluss:
Mithilfe der binären Suchtechnik kann ein sortiertes Array schnell nach einem bestimmten Element durchsucht werden. Es verwendet eine Divide-and-Conquer-Strategie, um den Suchbereich bei jeder Iteration zu halbieren, was eine hohe Effizienz bei großen Datensätzen ermöglicht. Vor der Verwendung der binären Suchtechnik muss jedoch das Eingabearray sortiert werden, was zusätzliche Zeit und Speicher erfordert. Der binäre Suchalgorithmus ist ein hochentwickeltes Datenverarbeitungstool, das in verschiedenen Branchen weit verbreitet ist.