浅谈二分查找的变种

之前我们谈过双指针的一些概念，其实就是二分查找啦，一般看到这种题目给我们排序好的数组，让我们从中找到某个符合条件的元素的时候，基本上都是想考二分查找。不过最近的面试官也很精明，会对题目稍微做一些改变，我们今天来看看一些简单的变法。

题目是这样的，给定一个排序好的数字数组，试着找出某个数字k是否存在。数组可能升序可能降序，而且可能有重复数字。写出一个函数，返回k的索引，如果没有返回-1。

乍一看这题目限制条件还挺多，为了让我们思考过程简单些，我们先假设数组是升序的。然后再来看看我们二分查找的步骤：

1. 让指针start指向数组的第一个元素，指针end指向数组的最后一个元素。
2. 找出start跟end的中间值middle，这里注意一下，通常我们找中值肯定习惯性的：middle=(start+end)/2。但是在Java里面，这肯能会导致溢出，当start=Integer.MAX_VALUE时，给它加个1都会溢出。安全的写法是：middle = start + (end-start)/2。
3. 比较middle指向的值跟k是否一样大，如果k<arr[middle]，那k肯定比数组后半段的数都小，那么end=middle-1；如果k>arr[middle]，那k肯定在数组后半段里面找那么start=middle+1。
4. 重复上面的步骤，如果最终出现了start>end的情况，那么说明数组里找不到这个数，返回-1。

至于数组的排序顺序，很好办，既然它是一个排序好的数组，我们直接比较首位两个值的大小就能轻松得到它是升序还是降序了。来看下实现：

public static int search(int[] arr, int k) {
        int start = 0, end = arr.length - 1;
        boolean isAscending = arr[start] < arr[end];
        while (start <= end) {
            // 缩小范围
            int mid = start + (end - start) / 2;

            if (k == arr[mid])
                return mid;

            if (isAscending) { // 升序
                if (k < arr[mid]) {
                    end = mid - 1; // 在前半段
                } else { 
                    start = mid + 1; // 在后半段
                }
            } else { // 降序
                if (k > arr[mid]) {
                    end = mid - 1; // 在前半段
                } else { 
                    start = mid + 1; // 在后半段
                }
            }
        }
        return -1; // 找不到
    }

这题本身很简单，只是隐藏了数组升序还是降序的信息，这种变通根本不能叫变通嘛！

先别激动，有了前面的铺垫之后，我们再来看一个在这基础上做的变通：给定一个升序排序的数字数组，找到给定数字k的天花板数字。k的天花板数字就是最小的大于等于k的数字。

哎呦，这个跟前面的东西有点像啊。我们还是在数组里搜索数字k，如果找到了，那它就是我们要找的天花板儿。否则的话把start设置成它的下一个数字。我们一直在调整这个范围，当我们退出这个循环的时候，start是不是刚好指在稍微大过k的数字上？你品，你细品！

public static int searchCeilingOfANumber(int[] arr, int k) {
        if (k > arr[arr.length - 1]) // 如果k大于数组最大元素
            return -1;

        int start = 0, end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (k < arr[mid]) {
                end = mid - 1;
            } else if (k > arr[mid]) {
                start = mid + 1;
            } else { // found the k
                return mid;
            }
        }
        // 循环会一直进行直到'start <= end', 所以在最后, 'start == end+1'
        // 这时候我们可以确定在数组里找不到k了, 所以比它稍微大一点的数是arr[start]
        return start;
    }

这两个算法因为我们每执行一次就缩短一半范围，所以时间复杂度都在O(logN)，N是数组大小，而我们没有额外开辟空间，空间复杂度一直维持在O(1)。

好了，今天我们只是粗略了解了一下二分查找简单的变种，其实复杂的情况也有很多，不过基本上也是在这基础上加一些其它的限制条件，我们只要掌握了题目核心知道了他用二分查找来做，对其它的特殊条件特殊处理就好。比如力扣上有一道搜索旋转数组问题就很有意思，今天我们就不拉长本文的篇幅，留到下次再说道吧。

关注我，一起交流算法吧