Java演算法關於二分查找法的範例講解

這篇文章主要介紹了java演算法之二分查找法的實例詳解的相關資料,這裡提供簡單實例幫助大家學習理解這部分內容，需要的朋友可以參考下

java演算法二分查找法的實例詳解

#原理

#假定查找範圍為有序數組（如昇序排列），要從中尋找某一元素，如果該元素在此數組中，則傳回其索引，否則傳回-1。透過數組長度可取出中間位置元素的索引，將其值與目標值比較，如果中間位置元素值大於目標值，則在左部分進行查找，如果中間位置值小於目標值，則在右部分進行查找，如此循環，直到結束。二分查找演算法之所以快是因為它沒有遍歷數組的每個元素，而僅僅是查找部分元素就能找到目標或確定其不存在，當然前提是查找範圍為有序數組。

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)); 
  } 
 
}

輸出結果為：

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

二分查找演算法的時間複雜度

假設範圍數組長度為N，則二分查找的時間複雜度為O（logN）

以上是Java演算法關於二分查找法的範例講解的詳細內容。更多資訊請關注PHP中文網其他相關文章！