Binäre Suche unter Java-Programmierung

Algorithmus: Diese Methode eignet sich, wenn die Datenmenge groß ist. Bei der binären Suche müssen die Daten in der richtigen Reihenfolge sein und dürfen sich nicht wiederholen. Grundidee: Nehmen Sie an, dass die Daten in aufsteigender Reihenfolge sortiert sind. Beginnen Sie den Vergleich an der mittleren Position der Sequenz. Wenn der aktuelle Positionswert gleich x ist, ist die Suche erfolgreich der aktuelle Positionswert, dann wird in der ersten Hälfte der Sequenz gesucht; wenn x größer als der aktuelle Positionswert ist, wird in der zweiten Hälfte der Sequenz weiter gesucht, bis er gefunden wird.

Angenommen, es gibt ein Array { 12, 23, 34, 45, 56, 67, 77, 89, 90 }. Jetzt muss die Binärmethode verwendet werden, um den angegebenen Wert zu finden und ihn an der Stelle zurückzugeben Index des Arrays. Wenn nicht gefunden, wird -1 zurückgegeben. Der Code lautet wie folgt:

package cn.sunzn.dichotomy;

public class DichotomySearch {
   public static void main(String[] args) {
       int[] arr = new int[] { 12, 23, 34, 45, 56, 67, 77, 89, 90 };
       System.out.println(search(arr, 12));
       System.out.println(search(arr, 45));
       System.out.println(search(arr, 67));
       System.out.println(search(arr, 89));
       System.out.println(search(arr, 99));
   }

   public static int search(int[] arr, int key) {
       int start = 0;
       int end = arr.length - 1;
       while (start <= end) {
           int middle = (start + end) / 2;
           if (key < arr[middle]) {
               end = middle - 1;
           } else if (key > arr[middle]) {
               start = middle + 1;
           } else {
               return middle;
           }
       }
       return -1;
   }
}

Weitere Artikel zur binären Suche in der Java-Programmierung finden Sie unter PHP Chinesische Website!