二分查找

基础思想

在一个大的区间内中的一个小区间进行查找，如果小区间中没有则排除这个区间再进行查找，不断的排除小区间，直到找到目标为止。二分查找的关键所在就是排除区间的条件。

例题

剑指Offer11

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

思路：设left和right分别指向数组的两端，设temp = (right + left)/2，分别有以下三种情况

num[temp] < num[left] 则目标数字一定在区间[left, temp]中

num[temp] > num[left] 则目标数字一定在区间[temp, right]中

num[temp] = num[left] 无法判断目标数字在哪个区间中，需要缩小判断区间，但是这种情况下，一定会有左区间或者右区间中数字全部相等，或两个区间都满足数字全部相等，可以放弃二分查找，直接线性查找

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int right = numbers.size() - 1;
        int left = 0;
        while(left < right){
            int temp = (right + left) / 2;
            if(numbers[temp] > numbers[right]){
                left = temp + 1;
            }
            else if(numbers[temp] < numbers[right]){
                right = temp;
            }
            else{
                int x = left;
                for(int i = left; i < right; i++){
                    if(numbers[i] < numbers[x]){
                        x = i;
                    }
                }
                return  numbers[x];
            }
        }
        return numbers[left];
    }
};

剑指Offer53-1

统计一个数字在排序数组中出现的次数。

输入: nums = [5,7,7,8,8,10], target = 8 输出: 2

思路：首先我们还是要判断二分循环的条件，同样的right,left,m

nums[m] < target，则target在右区间

nums[m] > target，则target在左区间

nums[m] = target，则target的右边界在右区间中，左边界在左区间中，又因为目标数字可能不止出现一次，所以我们得找到它的左右边界

寻找左边界：执行left = m - 1 寻找右边界：执行right = m + 1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i = 0, j = nums.size() - 1;
        while(i <= j){
            int m = i + (j - i) / 2;
            if(nums[m] <= target){
                i = m + 1;
            }else{
                j = m -1;
            }
        }
        int right = i;
        if(j >= 0 && nums[j] != target){
            return 0;
        }
        i = 0,j = nums.size() - 1;
        while(i <= j){
            int m = i + (j - i) / 2;
            if(nums[m] < target){
                i = m + 1;
            }else{
                j = m - 1;
            }
        }
        int left = j;
        return right - left - 1;
    }
};

优化：寻找边界可以抽象为一个函数用来寻找任意数字的边界，所以我们只需要寻找target的右边界和target - 1的右边界然后相减即可。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return searchBoundary(nums,target) - searchBoundary(nums,target - 1);
    }
private:
    int searchBoundary(vector<int>& nums, int target){
        int i = 0, j = nums.size() - 1;
        while(i <= j){
            int m = i + (j - i) / 2;
            if(nums[m] <= target){
                i = m + 1;
            }else{
                j = m - 1;
            }
        }
        return i;
    }    
};

剑指Offer53-2

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

思路：首先我们还是要判断二分循环的条件，同样的right,left,m，通过这个数组我们可以确定，如果是一个正常的递增数组，数组下标指和所指向的值是相对应的。如果不相对应，那么缺失的数字一定在m的右区间中。因为如果缺失数字在m的左区间中，则m绝对和它的下标值相对应。判断条件如下

当nums[m] == m 则缺失数字在左区间

当nums[m] != m 则缺失数字在右区间

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, rigth = nums.size() - 1;
        while(left <= rigth){
            int m = (left + rigth) / 2;
            if(nums[m] == m){
                left = m + 1;
            }else{
                rigth = m - 1;
            }
        }
        return left;
    }
};

总结

二分查找主要的解决方法就是确定判断的条件，但是不同的题目的判断条件具有很大的差异性，所以在解题的过程中需要仔细的验证条件的合理性