概述

本篇文章记录剑指offer标签为二分查找类的题。二分的模板太多了，本篇文章用的二分模板都是我之前发过的模板，附上链接：。下面的题都是在力扣上面做的，可以按照题名搜索即可

题不太多，建议刷刷leetcode上面二分的题，leetcode上面刷个10多道就够了

剑指 Offer 53 - II 0～n-1中缺失的数字

二分

由题意，我们可以将该数组分成两部分

第一部分是0 - x-1中, i = nums[i] , 第二部分是x - n - 1种中, i != nums[i]的则可以使用二分查找，我们要找到位置就是第一个i != nums[i]的位置。

边界情况是整个数组都是上图中蓝颜色的部分，我们要返回的值就是下一个数了

时间复杂度O(logN),空间复杂度O(1)

代码：

class Solution {
          
   
public:
    int getMissingNumber(vector<int>& nums) {
          
   
        if (nums.empty()) return 0;
        int l = 0 , r = nums.size() - 1;
        //二分查找，找到第一个 i != nums[i]的位置
        while ( l < r){
          
   
            int mid = l + r >> 1;
            if (mid != nums[mid]) r = mid;
            else l = mid + 1;
        }
        //边界情况，整个数组都是升序
        if (nums[l] == l) l ++;
        return l;
    }
};

剑指 Offer 53 - I 在排序数组中查找数字 I

二分

因为是排序好的数组，所以相同元素一定是连续存储在数组中的。要统计出现次数，我们只需要找到该数字在数组中第一次出现的位置和最后一次出现的位置即可。

我们需要做两次二分查找，找第一次个>=x的位置和第一个<=x的位置。这和二分模板是一模一样，具体想看模板请翻阅到文章的头部。

时间复杂度O(logN)，空间复杂度O(1)

代码：

class Solution {
          
   
public:
    int search(vector<int>& nums, int target) {
          
   
        //特判空数组
        if (nums.empty()) return 0;
        //第一次二分查找
        int start;
        int l = 0 , r = nums.size() - 1;
        while (l < r){
          
   
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid ;
            else l = mid + 1;
        }
        //数组不存在target
        if (nums[l] != target) return 0;
        start = l;
        //第二次二分查找
        l = 0 , r = nums.size() - 1;
        while (l < r){
          
   
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return l - start + 1;
    }
};

剑指 Offer 11 旋转数组的最小数字

二分

如图，本来是递增的序列经过旋转后会变成这样，前面一段是递增的，后面一段也是递增的。者两段是被第一个元素分割的

我们可以用二分找到第一段的最后一个位置，然后判断第二段是否存在

如果第二段存在，则第二段的第一个位置即最小元素 如果第二段不存在，则第一段的第一个元素为最小元素

该题由于有重复元素，我们所以可能存在第一段的开头和第二段的结尾可能都是相等的，我们需要用第一个元素作为两段的分割，因为存在相等元素，不能保证我们能够分清两端，所以需要将第二段末尾和第一段的第一个元素相同的删去。这样能够保证我们能够分割两段。

时间复杂度O(logN),O(1)

代码:

class Solution {
          
   
public:
    int minArray(vector<int>& nums) {
          
   
        //去除第二段和第一段第一个元素相同的元素
        int k = nums.size() - 1;
        while (k >= 0 && nums[k] == nums[0]) k --;
        //数组全是相同的
        if (k < 0) return nums[0];
        //二分，找到第一段最后一个元素
        int l = 0 , r = k ;
        while (l < r){
          
   
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        //判断第二段是否存在
        if (r == k) return nums[0];
        return nums[r + 1];
    }
};