Beispielerklärung des Java-Algorithmus zur binären Suchmethode

In diesem Artikel werden hauptsächlich relevante Informationen zur detaillierten Erläuterung der binären Suchmethode des Java-Algorithmus vorgestellt. Hier finden Sie ein einfaches Beispiel, das Ihnen beim Erlernen und Verstehen dieses Teils des Inhalts helfen kann

Java Detaillierte Erläuterung von Beispielen der binären Suchmethode des Algorithmus

Prinzip

Angenommen, der Suchbereich ist ein geordnetes Array (z. B in aufsteigender Reihenfolge) und Sie möchten ein bestimmtes Element daraus finden. Wenn sich das Element in diesem Array befindet, wird sein Index zurückgegeben, andernfalls wird -1 zurückgegeben. Der Index des mittleren Elements kann über die Länge des Arrays ermittelt werden und sein Wert wird mit dem Zielwert verglichen. Wenn der Wert des mittleren Elements größer als der Zielwert ist, wird die Suche im linken Teil durchgeführt Wenn der mittlere Positionswert kleiner als der Zielwert ist, wird die Suche im rechten Teil durchgeführt. Dieser Zyklus wird bis zum Ende fortgesetzt. Der Grund, warum der binäre Suchalgorithmus schnell ist, besteht darin, dass er nicht jedes Element des Arrays durchläuft, sondern nur nach einem Teil der Elemente sucht, um das Ziel zu finden oder festzustellen, dass es nicht existiert Bereich ist ein geordnetes Array.

Einfache Implementierung in Java

package me.geed.algorithms; 
 
public class BinarySearch { 
 
  /** 
   * 从一个有序数组(如升序)中找到值为key元素 
   * @param key 
   * @param array 
   * @return 如果找到目标元素，则返回其在数组中的索引，否则返回-1 
   */ 
  public static int find(int key, int[] array){ 
    int low = 0; 
    int high = array.length - 1; 
    while (low <= high) { 
      int mid = low + (high - low) / 2; 
      if (array[mid] > key) { 
        high = mid - 1; 
      } else if (array[mid] < key) { 
        low = mid + 1; 
      } else { 
        return mid; 
      }       
    } 
    return -1;    
  } 
   
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] array = {2, 3, 5, 9, 10, 13, 23, 45, 78, 89, 100, 128, 256}; 
    System.out.println("目标元素索引值：" + BinarySearch.find(9, array));     
    System.out.println("目标元素索引值：" + BinarySearch.find(26, array)); 
  } 
 
}

Das Ausgabeergebnis ist:

目标元素索引值：3 
目标元素索引值：-1

Zeitliche Komplexität des binären Suchalgorithmus

Angenommen, die Länge des Bereichsarrays beträgt N, dann beträgt die zeitliche Komplexität der binären Suche O(logN)

Das obige ist der detaillierte Inhalt vonBeispielerklärung des Java-Algorithmus zur binären Suchmethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!