二分查找算法又称为折半查找算法，该算法是John Mauchly在1946年提出的，它的优点是比较次数少，查找速度快，占用系统内存较少。缺点是对于待查找的数组要求是有序的，而且需要时采用顺序存储结构的数组。它比较适合数据稳定且查找频繁的场合。

算法复杂度为O(h) = O(log2n).

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 二分查找
 * @param key 目标数
 * @param array 待查数组
 * @return 目标数所在数组下标如果存在，否则返回-1
 */
public static int BinarySearch(int key, int[] array) {
  int lo = 0;
  int hi = array.length - 1;

  while(lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if(key < array[mid]) hi = mid - 1;
    else if (key > array[mid]) lo = mid + 1;
    else return mid;
  }
  return -1;
}