Java 資料結構 - 二分查詢

二分查詢是一種快速的搜尋演算法，其執行時複雜度為 Ο(log n)。這種搜尋演算法基於分治的原理。為了使該演算法正常工作，資料集合應該以排序的形式存在。

二分查詢透過比較集合中最中間的項來查詢特定項。如果匹配成功，則返回該項的索引。如果中間項大於該項，則在中間項左側的子陣列中搜索該項。否則，在中間項右側的子陣列中搜索該項。此過程繼續在子陣列上進行，直到子陣列的大小減小到零。

示例

public class BinarySearch {
   public static void main(String args[]) {
      int array[] =  {10, 20, 25, 57, 63, 96};
      int size = array.length;
      int low = 0;
      int high = size-1;
      int value = 25;
      int mid = 0;
      mid = low +(high-low)/2;

      while(low<=high) {
         if(array[mid] == value) {
            System.out.println(mid);
            break;
         } else if(array[mid]<value)
            low = mid+1;
            else high = mid - 1;
      }
      mid = (low+high)/2;      
   }
}

輸出

2