二分查找（Binary Search）算法也叫折半查找算法，针对的是一个有序的数据集合，它的查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素或区间被缩小为 0。下图展示了查找 19 这个元素的二分查找过程：

性能分析

二分查找是一种非常高效的查找算法，可以达到惊人的 O(logn)。假设数据大小是 n，每次查找后数据都会缩小为原来的一半，直到查找区间被缩小为空才停止。

可以看出，这是一个等比数列，其中 k 的值就是总共缩小的次数，而每一次缩小操作只涉及了两个数据的大小比较，所以经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

代码实现

下面，我们先来看如何来写最简单的二分查找。最简单的情况就是有序数组中不存在重复元素，我们在其中用二分查找值等于给定值的数据。

public static int search(int[] array, int value) {
    int min = 0;
    int max = array.length - 1;
    while (min <= max) {
        // 获取中间位置
        int middle = (min + max) / 2;
        if (array[middle] == value) {
            return middle;
        }
        if (array[middle] > value) {
            // 目标数据在中间位的左侧，所以max索引减1
            max = middle - 1;
        } else {
            // 目标数据在中间位的右侧，所以min索引加1
            min = middle + 1;
        }
    }
    return -1;
}

循环退出条件注意是 min<=max，而不是 min<max。
int middle = (min + max)/2 这种写法是有问题的，可能会导致整型溢出。改进的方法是将 middle 的计算方式写成 min+(max-min)/2。如果要将性能优化到极致可以将这里的除以 2 操作转化成位运算 min+((max-min)>>1)。
min 和 max 的更新如果直接写成 min=middle 或者 max=middle，就可能会发生死循环。

实际上，二分查找除了用循环来实现，还可以用递归来实现：

public static int search(int[] array, int value) {
    return searchInternally(array, 0, array.length - 1, value);
}
private static int searchInternally(int[] array, int min, int max, int value) {
    if (min > max) {
        return -1;
    }
    int middle = min + ((max - min) >> 1);
    if (array[middle] == value) {
        return middle;
    }
    if (array[middle] > value) {
        return searchInternally(array, min, middle -1, value);
    } else {
        return searchInternally(array, middle + 1, max, value);
    }
}

应用局限

二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。那什么情况下适合用二分查找，什么情况下不适合呢？

1）二分查找依赖顺序表结构，即数组
因为二分查找算法需要按照下标来随机访问元素，数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以如果使用链表来存储数据，二分查找的时间复杂就会变得很高。二分查找只能用在数据是通过顺序表来存储的数据结构上。如果你的数据是通过其他数据结构存储的，则无法应用二分查找。

2）二分查找针对的是有序数据
二分查找要求数据必须是有序的。如果数据不是有序则我们需要先排序，而排序的时间复杂度最低是 O(nlogn)。所以，如果我们针对的是一组静态数据，不会进行频繁插入、删除操作，那我们可以进行一次排序，多次二分查找，这样排序的成本可被均摊，二分查找的边际成本就会比较低。但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的。

所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。

3）数据量太小不适合二分查找
如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。只有数据量比较大的时候，二分查找的优势才会比较明显。不过，如果数据之间的比较操作非常耗时，不管数据量大小，我都推荐使用二分查找。

4）数据量太大也不适合二分查找
二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。

二分查找变形问题

我们上面写的二分查找是最简单的一种，即有序数据集合中不存在重复的数据，查找值等于某个给定值的数据。下面我们来看一些二分查找的变形问题，问题中涉及的数组都是有序，且存在重复元素的。

1. 查找第一个值等于给定值的元素

对于有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据。比如一个有序数组 a，其中，a[5]、a[6]、a[7] 的值都是 8。我们希望查找第一个等于 8 的数据，即下标是 5 的元素。

如果用之前的二分查找的代码实现，首先拿 8 与区间的中间值 a[4] 比较，8 >6，于是在 a[5…9] 之间继续查找。a[7] 正好等于8，所以代码就返回了。尽管 a[7] 也等于8，但它并不是我们想要找的第一个等于 8 的元素。针对这个变形问题，我们可以稍微改造一下上面的代码。

public static int search(int[] array, int value) {
    int min = 0;
    int max = array.length - 1;
    while (min <= max) {
        int middle = min + ((max - min) >> 1);
        if (array[middle] > value) {
            // 目标数据在中间位的左侧，所以max索引减1
            max = middle - 1;
        } else if (array[middle] < value) {
            // 目标数据在中间位的右侧，所以min索引加1
            min = middle + 1;
        } else {
            // 如果命中，则判断它的前一个元素是否也命中，middle为0则表示前面没数据了
            if (middle == 0 || array[middle - 1] != value) {
                return middle;
            } else {
                max = middle - 1;
            }
        }
    }
    return -1;
}

因为我们求解的是第一个值等于给定值的元素，所以当 array[middle] 的值等于要查找的值时，我们需要确认下 array[middle] 是不是第一个值等于给定值的元素。重点看第 14 行代码。

如果 middle 等于0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；
如果 array[middle-1] 不等于 value，说明 array[middle] 就是我们要找的第一个值等于给定值的元素
如果 array[middle-1] 等于 value，说明此时的 array[middle] 肯定不是我们要查找的第一个值等于给定值的元素。那就要更新 max=middle-1，因为要找的元素肯定出现在 [min, middle-1] 之间。

2. 查找最后一个值等于给定值的元素

public static int search(int[] array, int value) {
    int min = 0;
    int max = array.length - 1;
    while (min <= max) {
        int middle = min + ((max - min) >> 1);
        if (array[middle] > value) {
            max = middle - 1;
        } else if (array[middle] < value) {
            min = middle + 1;
        } else {
            if (middle == max || array[middle + 1] != value) {
                return middle;
            } else {
                min = middle + 1;
            }
        }
    }
    return -1;
}

我们还是重点看第 11 行代码。如果 array[middle] 这个元素已经是区间中的最后一个元素了，那它肯定是我们要找的；如果 array[middle+1] 不等于 value，那也说明 array[middle] 就是我们要找的最后一个值等于给定值的元素。如果 array[middle+1] 等于 value，那说明当前的这个 array[middle] 并不是最后一个值等于给定值的元素。我们就更新 min = middle + 1，因为要找的元素肯定出现在 [middle+1, max] 之间。

3. 查找第一个大于等于给定值的元素

再来看另外一类变形问题。在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。实际上，实现的思路跟前面的那两种变形问题的实现思路类似，代码写起来甚至更简洁。

public static int search(int[] array, int value) {
    int min = 0;
    int max = array.length - 1;
    while (min <= max) {
        int middle = min + ((max - min) >> 1);
        // 如果大于等于给定值，则判断它的前一个元素是否也大于等于给定值
        if (array[middle] >= value) {
            if (middle == 0 || array[middle - 1] < value) {
                return middle;
            } else {
                max = middle - 1;
            }
        } else {
            min = middle + 1;
        }
    }
    return -1;
}

如果 array[middle] 小于要查找的值 value，那要查找的值肯定在 [middle+1, max] 之间，所以，我们更新 min = middle + 1。对于 array[middle] 大于等于给定值 value 的情况，我们要先看下这个 array[middle] 是不是我们要找的第一个值大于等于给定值的元素。如果 array[middle] 前面已经没有元素，或者前面一个元素小于要查找的值 value，那 array[middle] 就是我们要找的元素。这段逻辑对应的代码是第 8 行。如果 array[middle-1] 也大于等于要查找的值 value，那说明要查找的元素在 [min, middle-1]之间，所以将 max 更新为 middle-1。

4. 查找最后一个小于等于给定值的元素

public static int search6(int[] array, int value) {
    int min = 0;
    int max = array.length - 1;
    while (min <= max) {
        int middle = min + (((max - min)) >> 1);
        if (array[middle] > value) {
            max = middle - 1;
        } else {
            if (middle == array.length - 1 || array[middle + 1] >= value) {
                return middle;
            } else {
                min = middle + 1;
            }
        }
    }
    return -1;
}