你真的会用二分查找吗？

嗯，其实最简单的二分查找写起来还是挺简单的，稍微注意下可能出错的地方即可。用循环还是递归都可以，我这里先写一个 你们也可以搜一下有没有更好的写法

/**
     * 二分查找
     * @param a  源数组 注意这个数组的值一定是经过 排序 的有序数组
     * @param n  数组大小
     * @param key 想要查找位置的值
     * @return
     */
    public int search(int[] a, int n, int key) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            //这个地方 计算mid的值 有可能会发生 越界异常的，low+high 非常有可能超过int的最大值限制
            //所以这边可以优化成low+(high-low)/2  甚至用到位运算low+((high-low)>>1)
            int mid = (low + high) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
复制代码

但是注意了，这里只是最简单的二分查找，实际生产中，我们可能面对的是：

找出第一个值等于key的元素，或者找出最后一个值等于key的元素，甚至还有找出第一个<= 或者>=的元素位。

这种二分查找写起来就比较麻烦而且很容易出bug了，有兴趣的同学可以去leetcode上写一下玩一玩。

真正生产环境中二分查找还是用在 这种近似查找的地方比较多，真正意义上的 准确查找，我们还是用hashmap，二叉树来

做得比较多，因为这2种做准确查找有额外优势（虽然这2个需要额外内存空间）

二分查找啥时候用比较合适？

首先要注意的是，二分查找速度还是挺快的，千万不要以为他写起来简单就认为他不快。。这和写起来简单跑起来十分缓慢的 冒泡排序是两码事。毕竟是O(logn)的速度，就算你有2的32次方大概40多亿的数据量要查一个数据，最多也就32次就可以查完。

但是二分查找仍旧有自己的局限性：

1. 二分查找需要数据源是数组假设我们二分查找用在链表为数据结构的地方，可以想一下，链表的随机访问长度时间 复杂度是O(n)。 我们可以还原一下这个场景：假设用二分查找在链表上，那么第一次找到这个mid的位置 要移动n/2次，第二次找到mid的位置要移动n/4,以此类推n/8,n/16，可以看出来这个寻找 mid的操作时间复杂度就是O(n),再想想其他操作， 这个实际的运行时间肯定比顺序查找要慢了 ， 所以二分查找不可以用在链表上，只能用在数组上

2. 二分查找必须要求数据源是有序的，且数据源最好是静态的，动态的数据源多数场景不使用二分查找。 因为二分查找必须要求数据源是有序的，所以如果我们数据源不是有序数据，就必须先进行排序才能查找。排序当然也 是耗时的，最快也要O(nlogn)，所以如果你要查找的数据源频繁的插入删除，需要频繁的重新排序的话，用二分查找 就很慢了。

3. 数据量太多就别用二分查找了，数据量太小也别用，特殊情况最好用。 前面说到二分查找要用数组来做 数据结构，如果你这里数据量太大，那么你需要的内存空间就太大了，比方说你剩余内存是4gb，你的数据有3.8gb， 那么大概率这里你用二分查找要失败，因为数组要求的是连续内存空间，我们剩余内存有4gb，可不代表着4个gb的剩余空间是连续的。

数据量太小为啥也不用呢，其实你要用也不是不可以，主要是数据量太少，二分查找优势不明显，写起来还麻烦，省事的话 数据量小就用顺序查找吧。有一种情况特殊，比如我们的二分查找的比较操作比较耗时的话就最好用二分查找了，也就是 说单次比较操作耗时的查找（比方说长度很长超过500左右的大字符串比较），最好用二分查找，因为二分查找可以大幅减少比较的次数。

本宝宝就是头硬，非要在链表上实现二分查找怎么办，而且还不能慢？

计算机界有两句名言。 1.计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。2.如果时间不够就用空间来换， 如果空间不够，就用时间来换。

所以，如果想在链表上实现二分查找有序集合还不能慢的话，用空间换时间就是一个好方法。“跳表” 就是一个很有效的解决方案。 简单来说所谓跳表就是对一个链表 建立n个索引层，然后查找的时候 通过索引层来找即可。我画了个草图大家可以体会下：

很好理解吧，其实 redis 的有序集合也用的这个。 只不过跳表这个解决方案出现的比较晚，很多sdk都没有跳表的实现，但是 红黑树的实现很多，所以跳表知道的人不多。因为索引的存在，在区间查找的时候跳表甚至比红黑树还要快一些。

跳表的具体实现大家可以自行百度学习，比如这个链接就不错

这里只做开拓视野，让大家知道有这么回事即可。有兴趣的同学可以自己写写看，跳表的插入删除和索引更新的策略都是蛮有意思 的东西。