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