Java-Codebeispiel zur Implementierung der binären Suche

In diesem Artikel werden hauptsächlich relevante Informationen zur Java-Binärsuche vorgestellt. Freunde, die sie benötigen, können auf den

Algorithmus

zugreifen Die Anzahl der Gruppen beträgt 3, 12, 24, 36, 55, 68, 75, 88. Um den angegebenen Wert zu überprüfen, 24. Sie können drei Variablen vorne, mitte, end festlegen auf die obere, mittlere und untere Grenze der Daten zeigen, Mitte=(Front+Ende)/2. 　　

Beginnen Sie mit Front=0 (zeigt auf 3), Ende=7 (zeigt auf 88) , dann mid=3 (zeigt auf 36) ). Da „mid>x“ in der ersten Hälfte des Absatzes gesucht werden sollte.

Lassen Sie das neue Ende = Mitte-1 = 2 und die Vorderseite = 0 unverändert, dann ist die neue Mitte = 1. Zu diesem Zeitpunkt ist x>mid, daher muss in der zweiten Hälfte gesucht werden.

Lassen Sie die neue Front = Mitte + 1 = 2 und Ende = 2 unverändert, dann ist die neue Mitte = 2, zu diesem Zeitpunkt a [Mitte] = x, die Suche ist erfolgreich. Wenn die zu suchende Zahl keine Zahl in der Folge ist, zum Beispiel x = 25, ist bei der dritten Beurteilung x> a [mid] gemäß den obigen Regeln front = mid + 1, d , front=3 und front>end werden angezeigt. Im Fall von

bedeutet dies, dass die Suche nicht erfolgreich war.

Beispiel: Finden Sie die vom Benutzer eingegebenen Daten x in einem geordneten Array mit N Elementen. Der Algorithmus lautet wie folgt:

1. Bestimmen Sie den Suchbereich front=0, end=N-1 und berechnen Sie den Mittelterm mid=(front+end)/2.

2. Wenn a[mid]=x oder front>=end, beenden Sie die Suche, andernfalls fahren Sie fort.

3. Wenn a[mid]d700112d493b8b5a61d2008b95527d25x bedeutet, dass der Wert des zu findenden Elements nur in einem kleineren Bereich als das mittlere Element liegen kann, weisen Sie dann den Wert mid-1 zu Um den Wert zu beenden und die Mitte neu zu berechnen, fahren Sie mit Schritt 2 fort.

Algorithmus-Komplexitätsanalyse

Zeitkomplexität

1. Schlimmste Situation Finden Sie die letztes Element (oder erstes Element) Satz des Meisters T(n)=T(n/2)+O(1) also T(n)=O(logn)

2. Am besten, wenn die Mitte gefunden wird Element O(1), das gesuchte Element ist das mittlere Element (das mittlere Element der Sequenz ungerader Länge, das mittlere linke Element der Sequenz gerader Länge)

Raumkomplexität:

S(n)=n

package com.bjpowernode.test;
public class BinarySearch {
  // 查找次数
  static int count;
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    System.out.println(searchRecursive(array, 0, array.length - 1, 9));
    System.out.println(count);
    count = 0;
    System.out.println(searchLoop(array, 9));
    System.out.println(count);
  }
  /**
   * 执行递归二分查找，返回第一次出现该值的位置
   *
   * @param array
   *      已排序的数组
   * @param start
   *      开始位置
   * @param end
   *      结束位置
   * @param findValue
   *      需要找的值
   * @return 值在数组中的位置，从0开始。找不到返回-1
   */
  public static int searchRecursive(int[] array, int start, int end,
      int findValue) {
    // 如果数组为空，直接返回-1，即查找失败
    if (array == null) {
      return -1;
    }
    count++;
    if (start <= end) {
      // 中间位置
      int middle = (start + end) / 1;
      // 中值
      int middleValue = array[middle];
      if (findValue == middleValue) {
        // 等于中值直接返回
        return middle;
      } else if (findValue < middleValue) {
        // 小于中值时在中值前面找
        return searchRecursive(array, start, middle - 1, findValue);
      } else {
        // 大于中值在中值后面找
        return searchRecursive(array, middle + 1, end, findValue);
      }
    } else {
      // 返回-1，即查找失败
      return -1;
    }
  }
  /**
   * 循环二分查找，返回第一次出现该值的位置
   *
   * @param array
   *      已排序的数组
   * @param findValue
   *      需要找的值
   * @return 值在数组中的位置，从0开始。找不到返回-1
   */
  public static int searchLoop(int[] array, int findValue) {
    // 如果数组为空，直接返回-1，即查找失败
    if (array == null) {
      return -1;
    }
    // 起始位置
    int start = 0;
    // 结束位置
    int end = array.length - 1;
    while (start <= end) {
      count++;
      // 中间位置
      int middle = (start + end) / 2;
      // 中值
      int middleValue = array[middle];
      if (findValue == middleValue) {
        // 等于中值直接返回
        return middle;
      } else if (findValue < middleValue) {
        // 小于中值时在中值前面找
        end = middle - 1;
      } else {
        // 大于中值在中值后面找
        start = middle + 1;
      }
    }
    // 返回-1，即查找失败
    return -1;
  }
}

Das obige ist der detaillierte Inhalt vonJava-Codebeispiel zur Implementierung der binären Suche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!