相信大家都玩过小时候的猜数字游戏：A想一个100以内的数，大家来猜这个数，谁的次数最少谁就获胜。这大概是我们最早接触二分查找了，二分查找是查找算法中效率比较高而且也比较简单的算法，但是使用上会有一些限制，比如需要查找集合是顺序存储的有序表。

---

一、简述

二分查找又叫折半查找，需要在顺序存储有序表（随机访问）中进行查找。

它的整体思想比较简单易懂，先与顺序表中间元素进行对比，

• 等于中间元素则查找成功；
• 大于中间则在右边子表以同样的方式查询；
• 小于中间则在左边子表以同样的方式查询；

（注意上面的大于小于等于只是抽象的概念，并非只是数字比较，具体的规则有我们自己定义。）

二、算法实现

1、迭代（非递归）

int binarySearch(int key, int[] array, int low, int high) {
    if (array.length == 0 || low < high ||
            key > array[high] || key < array[low]) {
        return -1;
    }
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == array[mid]) {
            return mid;
        } else if (key < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

2、递归

一般来说二分用迭代循环就好了，不推荐用递归，递归的空间消耗更大。这里可以加深下递归思想的理解。

int binarySearch(int key, int[] array, int low, int high) {
    if (array.length == 0 || low > high ||
            key > array[high] || key < array[low]) {
        return -1;
    }
    if (low <= high) {
        int mid = (low + high) / 2;
        if (key == array[mid]) {
            return mid;
        } else if (key < array[mid]) {
            return binarySearch(key, array, low, mid - 1);
        } else {
            return binarySearch(key, array, mid + 1, high);
        }
    }
    return -1;
}

三、分析

每次查找的范围减少一半，很明显二分查找的时间复杂度是 O(h)=O(lgn) 

二分查找很快，但是限制条件也比较多，光是有序条件就比较麻烦，如果维护有序的代价不小的话，就需要权衡了。