算法二分查找算法篇

困而学，学而知

什么是二分查找算法呢？

首先需要说明的是，只要在数组有序的情况下，二分查找才是有用。如果是一个无序的数组，二分查找就没有意义了。

现在有1~100个数，当然是有序的，现在需要你猜一个数。你每猜一次，我告诉你猜大了还是猜小了，那么现在开始吧。

现在有三种方案

1. 从1按照顺序猜

   我们来看看这种方式，如果从1按照顺序猜，最好的情况就是第1次就猜中，最坏的情况就是最后一次才会猜中。

2. 第二种方案是乱猜，这种方案和第一种方案的的结果是一样，最好就是首次就猜中，最坏情况也是就是最后才猜中。

3. 第三种方案则是使用我们今天要说二分查找法，那又如何使用二分查找法来猜呢？这种方案的最好和最坏的情况又分别的是什么，也就是和上面的两种方案比起来提升点到底在哪里呢？容我慢慢道来。

如何使用二分查找

• 找到1和100中间的数字，也就是50。我会告诉你大了还是小了，也可能运气好第一次就猜中了?

• 我说大了，那你继续猜25，1和50中间的数字。我会告诉你小了。这时候我们就排除了比50打的数字，是不是对半分了，也就是所说的二分。
  

• 继续猜38，26和50中间的数字，我说大了，这时候又会继续去找26到38之前的数字。

  …

• 以此类推，到最终找到我们想要的数字，最多会找几次呢？7次

使用二分查找和上面两种方式的对比

显而易见的，如果使用二分查找，最好的情况都是一样的，以第1次就能查到。但是最坏的情况则不然，其他两种情况，最坏的情况需要100次，而使用二分查找只需要7次，效率显而易见。

专业人士就需要用专业解释。使用第一种方案查询是一种线性查询，查询的次数会根据需要查询的数量递增。也就是如果有n个数字，最多就需要查询n次。而使用二分查找最多只需要log₂n次。（先不唠叨这个，后续会有单独的文章来唠叨）

从上面的对比来看，这个提升点肯定是在查询的次数上面了。那么还有其他的提升呢？

其实在算法的效率的对比上面一直有两个重要的点：空间和时间。上面我们比较了空间复杂度，我们现在来看看他们的时间复杂度。

时间复杂度

这里直接说结论吧，第一种方案的时间复杂度是：O(n)，二分查找法的时间复杂度是：O(logn)

这里不唠叨大O表示法，后面紧跟着唠叨。

想象一下，在亿的数量下，二分查找的效率有多高。

MySQL中B+树中节点内部数据查询就是用到了二分查找法

上菜

话不多说，直接上菜。

private static int binarySearch(long[] arr, int item) {
        int low = 0;
        // 最打的数字是数组长度-1
        int high = arr.length - 1;
        // 为什么是'<='？ 因为如果直接使用arr.length可能会出现越界,
        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = arr[mid];

            if (midVal < item) {
                low = mid + 1;
            } else if (midVal > item) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19