---

概述

本篇文章記錄劍指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];
    }
};

r = mid - 1;
}
//判斷第二段是否存在
if (r == k) return nums[0];
return nums[r + 1];
}
};