为什么二分查找一定要求数组有序呢

Question

c语言数据结构憨批问题。                  

Answer 1

1. 二分查找法介绍

1.1 二分查找法概念

先来一段维基百科概念。“二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。”

简单来说，就是在序列中找到一个分割点，使得我们需要找的答案一定在某一边的子序列而不在另一边的子序列，之后继续在找到子序列中给出分割点，无限二分下去直到找到目标，这使得原本需要一次遍历的查找时间复杂度降为了O ( lg ⁡ N ) O(\lg N)O(lgN).

这里有很重要的一点是：使用二分查找不一定要求数组是有序的。只需要能够找到一个分割点，将序列分为两个类别即可，通常来说这个分割点用中点。上述最基础的二分法是分为哪两个类别呢？小于中间值的为一类，大于中间值的为另一类。如果在无序的数组中，可以将数组按不同的方法分类。

这里，可以给出一个无序数组使用二分查找的例子：

Leetcode[162] Find Peak Element

【题干】峰值元素是指其值大于左右相邻值的元素。给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。

【题解】峰值的必然存在性使得我们是可以用二分法来进行处理。先找出序列最中间的值nums[mid]，如果当前值相比于其右边的值更大，说明左半边必然有一个峰值；否则右半边必然有一个峰值。由于本题要求是找到一个峰值即可，因此使用二分法是可行的。

本题是如何分类的：一边必然至少有一个峰值；一边不确定有没有峰值。因此我们二分可以放弃另一边来减少搜索次数。

【代码】

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1;
    while(l < r){
        int mid = l + r >> 1;               //中间点
        if(nums[mid] > nums[mid + 1]) r = mid;
        else l = mid + 1;
    }
    return l;
}

因此，记住一点，使用二分法不一定要求有序，只要求可以确定答案一定会出现在其中一边即可。

1.2 二分法类型

使用二分法的题有两种类型，一种是序列的二分查找，一种是数值的二分查找。

序列的二分查找类似上述的常规二分，一半都是给定一个序列，找到符合某个要求的值。二维序列的二分查找事实上和一维序列类似，这里不将其分为两类。

数值的二分查找即给定一个数字和一些条件，并且可以知道答案必然在这个数字（或整数最大值）和某个值（通常为0或1）之间。

之后分别给出这两种类型问题的二分模版。

1.3 二分法模版

• 序列二分模版（1）

public int binarySearch(int[] nums){
    int l = 0, r = nums.length - 1;
    while(l < r){
        int mid = l + ((r - l) >> 1);   //整数不溢出可以写成 ： l + r >> 1
        if(check(mid, xxx) == true) r = mid;
        else l = mid + 1;
    }
    return l;
}

【注意1】为了避免发生l + r发生整数溢出的情况，最好写成 mid = l + ((r - l) >> 1)

【注意2】关于中点，该模版为左区间闭右区间开型。[l, mid] (mid, r]

【注意3】该模版可以找到符合条件的最左边的值。

例如在序列[1,3,5,7,7,7,7,7,7,8,8,10]中寻找7，使用该模版将返回3，即第一个7出现的位置

• 1

• 序列二分模版（2）

public int binarySearch(int[] nums){
    int l = 0, r = nums.length - 1;
    while(l < r){
        int mid = r - ((r - l) >> 1);    //整数不溢出可以写成 ： l + r + 1 >> 1
        if(check(mid, xxx) == true) l = mid;
        else r = mid - 1;
    }
    return r;
}

【注意1】为了避免发生l + r + 1发生整数溢出的情况，最好写成 mid = r - ((r - l) >> 1)

【注意2】关于中点，该模版为左区间开右区间闭型。[l, mid) [mid, r]

【注意3】该模版可以找到符合条件的最右边的值。

例如在序列[1,3,5,7,7,7,7,7,7,8,8,10]中寻找7，使用该模版将返回8，即最后一个7出现的位置

• 1

• 数值二分模版

public int binarySearch(int n){
    int l = 1, r = n;           //有时写成 ：int l = 1, r = Integer.MAX_VALUE;
    while(l < r){
        int mid = l + ((r - l) >> 1);   //整数不溢出可以写成 ： l + r >> 1
        if(check(mid, xxx) == true) r = mid;
        else l = mid + 1;
    }
    return l;
}

数值二分其实没区别，就是初始值稍微有所不同。

2. 二分法实例及模版测试

2.1 leetcode[33] Search in Rotated Sorted Array【中等】

【题干】升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

【题解】如果使用暴力法，只需要扫描遍数组即可完成，但一道中等题显然不会这么简单，因此考虑二分查找。由于数组进行了旋转，所以整体并不是有序的。但有两点需要注意：（1）以轴为分界线的左子序列是单调递增的，右子序列也是单调递增的 （2）左子序列全大于或等于nums[0]，右子序列全小于nums[0] 。 因此使用二分法时可利用这两个注意点并得到：

（1）若目标值大于或等于num[0]，则结果必然出现在左子序列，此时检查mid值，若小于num[0]则必不存在mid右边，又因为左子序列单调递增，若mid值大于目标，必然目标不在mid右边，如下图：

（2）若目标值小于num[0]，则结果必然出现在右子序列，此时检查mid值，若小于num[0]且大于目标值才会出现在mid左侧，如下图：

【代码】

   public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(check(nums, target, mid) == true) r = mid;
            else l = mid + 1;
        }
        if(l >= nums.length || nums[l] != target) return -1;
        return l;
    }
    
    private static boolean check(int[] nums, int target, int mid){
        if(target >= nums[0]){
            if(nums[mid] < nums[0] || nums[mid] >= target) 
                return true;
            else 
                return false;
        }
        else{
            if(nums[mid] >= target && nums[mid] < nums[0])
                return true;
            else
                return false;
        }
    }

2.2 leetcode[74] Search a 2D Matrix【中等】

【题干】编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

【题解】这是一道二维序列的二分搜索，这题只需要在第一维进行二分搜索，再在搜索结果中进行二分搜索即可。

【代码】

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(matrix[mid][0] >= target) r = mid;
            else if(matrix[mid][n - 1] < target) l = mid + 1;
            else{
                l = mid;
                break;
            }
        }
        if(l >= matrix.length) return false;
        int a = 0, b = matrix[0].length - 1;
        while(a < b){
            int mid = a + b >> 1;
            if(matrix[l][mid] >= target) b = mid;
            else a = mid + 1;
        }
        if(a >= matrix[0].length || matrix[l][a] != target) return false;
        else return true;
    }

2.3 leetcod[875] Koko Eating Bananas

【题干】珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

【题解】首先明确珂珂吃香蕉的速度上限和下限，上限是香蕉堆的香蕉数目最大值，题目给定1000000000，下限是1根。我们使用二分来查找最终结果，mid是珂珂当前的测试速度。如果某堆香蕉数目大于mid，则珂珂无法在一个小时内吃完，因此相当于将这堆香蕉分为若干小堆，保证每堆都可以在一个小时内吃完。因而我们的目标是，将香蕉分为H堆，并且每堆尽可能小，每堆香蕉数量不大于k。因此，没找到一个mid，测试以此速度吃香蕉时，香蕉的堆数，如果堆过少，说明吃香蕉的速度需要放慢一些；如果堆过多，说明吃香蕉速度需要加快一些。

【代码】

    public int minEatingSpeed(int[] piles, int H) {
        int l = 1, r = 1000000000;
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid, H, piles) == true) r = mid;    //测试堆数与H的关系
            else l = mid + 1;
        }
        return l;
    }
    
    private static boolean check(int mid, int H, int[] piles){
        int idx = 0, count = 0;
        while(idx < piles.length){       //统计以此速度吃完的堆数
            if(piles[idx] > mid){
                int num = piles[idx]/mid;
                count += num + 1;
            }
            else
                count += 1;
            idx++;
        }
        if(count <= H) return true;
        else return false;
    }

2.4 其他二分题

• 利用模版可以解决包括且不限于下列题目：

• Leetcode[29] Divide Two Integers

• Leetcode[34] Find First and Last Position of Element in Sorted Array

• Leetcode[35] Search Insert Position

• Leetcode[81] Search in Rotated Sorted Array II

• Leetcode[153] Find Minimum in Rotated Sorted Array

• Leetcode[154] Find Minimum in Rotated Sorted Array II

• Leetcode[275] H-Index II

• Leetcode[278] First Bad Version

3. 小结

• 数组有序不是二分查找的必要条件，要更加实际情况考虑，只需要可以区分左右即可二分
• 整数溢出问题要多加小心
• 模版（1）会找出最左侧的目标值，模版（2）会找出最右侧的目标值