[JAVA] Algorithmusgymnastik 1

Binary Search on Arrays

Erläuterung

Ein Array, in dem die sortierten Ganzzahlen und der gesuchte Schlüssel gespeichert sind, wird übergeben. Wenn sich dieser Schlüssel in einem Array befindet, wird der Index des Schlüssels zurückgegeben. Wenn der Schlüssel nicht vorhanden ist, wird -1 zurückgegeben.

Beispiel

Array mit 47 Schlüsseln und 20 Elementen

Solution

Runtime Complexity: O(logn) Memory Complexity: O(logn)

Die binäre Suche wird verwendet, um den Index eines Elements in einem sortierten Array zu finden. Wenn das Element nicht vorhanden ist, kann es gleichermaßen effizient gefunden werden. Der Algorithmus teilt das Eingabearray bei jedem Schritt in zwei Hälften. Nach jedem Schritt können Sie die Hälfte des Arrays verwerfen, um festzustellen, ob der gesuchte Index gefunden wurde. Daher kann die Lösung in O (logn) Zeit berechnet werden.

Grober Algorithmusfluss

1. Bestimmen Sie das Tief des kleinsten Index und das Hoch des größten Index, die der von Array zu untersuchende Bereich ist.
2. Ermitteln Sie den Wert von mid im Mittelpunkt von low und high.
3. Wenn das Element im Index von mid mit dem Schlüssel identisch ist, geben Sie mid zurück.
4. Wenn es größer als das Element im Index von mid ist, ist high = mid -1. (Niedrig bleibt wie es ist)
5. Wenn es kleiner als das Element im Index von mid ist, ist low = mid + 1. (Hoch bleibt gleich)
6. Wenn jedoch niedrig größer als hoch wird, ist der Schlüssel nicht vorhanden, sodass -1 zurückgegeben wird.

code

Ergänzung

Die iterative Methode, bei der die Radschleife anstelle der rekursiven Methode verwendet wird, weist dieselbe Geschwindigkeitseffizienz auf, die Raumkomplexität kann jedoch O (1) sein.