Zweiteilige Partition

Definition

Die binäre Suchmethode ist ein Algorithmus, dessen Eingabe eine geordnete Liste von Elementen ist.

Wenn das gesuchte Element in der Liste enthalten ist, gibt die binäre Suche seine Position zurück. andernfalls wird null zurückgegeben.

Grundgedanke

1. Diese Methode eignet sich, wenn die Datenmenge groß ist.
2. Bei der binären Suche müssen die Daten sortiert werden
3. Angenommen, die Daten sind in aufsteigender Reihenfolge sortiert. Beginnen Sie den Vergleich für einen gegebenen Wertschlüssel an der mittleren Position in der Mitte der Sequenz:
4. Wenn der Wert von arr[mid] an der aktuellen Position gleich dem Schlüssel ist, ist die Suche erfolgreich;
5. Wenn der Schlüssel kleiner als der aktuelle Positionswert arr[mid] ist, dann suchen Sie in der ersten Hälfte der Sequenz nach arr[low,mid-1].
6. Wenn der Schlüssel größer als der aktuelle Positionswert arr[mid] ist, suchen Sie in der zweiten Hälfte der Sequenz weiter nach arr[mid+1,high], bis er gefunden wird.

Zeitliche Komplexität: