二分查找题型总结

1、经典二分查找：递增序列找target

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

2、非递减序列找到第一个比target更大/非递增序列找到第一个比target更小的

class Solution {
public:
    //  这种方法可以在非递减序列中找到第一个大于目标值的数
    char nextGreatestLetter(vector<char>& letters, char target) {
        if(letters[letters.size()-1]<=target){
            return letters[0];
        }
        int n = letters.size();
        int left = 0, right = n-1;
        while(left < right){
            int mid = left +(right-left)/2;
            if(letters[mid] <= target){
                // 往右找
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return letters[left];
    }
};

或者：

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        if(letters[letters.size()-1]<=target){
            return letters[0];
        }
        int n = letters.size();
        int left = 0, right = n-1,ans;
        while(left <= right){
            int mid = left +(right-left)/2;
            if(letters[mid] <= target){
                left = mid+1;
            }else {
                ans = mid;
                right = mid-1;
            }
        }
        return letters[ans];
    }
};

3、非递减序列找到第一个等于target的下标

下面这个题需要分别找第一个等于target的下标和最后一个等于target的下标

int binarySearch_1(vector<int>& nums, int target){
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while(left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid-1;
            }else if(nums[mid] == target){
                right = mid-1;
                ans = mid;
            }else {
                left = mid+1;
            }
        }
        return ans;
    }

4、非递减序列找到最后一个等于target的下标

// 查找最后一个等于target的下标
    int binarySearch_2(vector<int>& nums, int target, bool lower){
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while(left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid-1;
            }else if(nums[mid] == target){
                left = mid+1;
                ans = mid;
            }else {
                left = mid+1;
            }
        }
        return ans;
    }

5、非递减序列找到最后一个小于target的下标

int binarySearch_4(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1,ans= -1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] >= target){
                right = mid-1;
            }else {
                ans = mid;
                left = mid+1;
            }
        }
        return ans;
    }

总结

// 查找第一个等于 target的下标
    int binarySearch_1(vector<int>& nums, int target){
    	// ans需要初始化，初始化为0或者nums.size()都行
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while(left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid-1;
            }else if(nums[mid] == target){
                right = mid-1;
                ans = mid;
            }else {
                left = mid+1;
            }
        }
        return ans;
    }

    // 查找最后一个等于target的下标
    int binarySearch_2(vector<int>& nums, int target){
   		 // ans需要初始化，初始化为0或者nums.size()都行
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while(left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid-1;
            }else if(nums[mid] == target){
                left = mid+1;
                ans = mid;
            }else {
                left = mid+1;
            }
        }
        return ans;
    }

    // 查找第一个大于target的下标
    int binarySearch_3(vector<int>& nums, int target) {
    	// ans初始化为nums.size()，是因为可能存在所有的数都小于等于target的情况
        int left = 0, right = nums.size()-1,ans= nums.size();
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] <= target){
                left = mid+1;
            }else {
                ans = mid;
                right = mid-1;
            }
        }
        return ans;
    }

    // 查找最后一个小于target的下标
    int binarySearch_4(vector<int>& nums, int target) {
    // ans初始化为-1，是因为可能存在所有的数都大于等于target的情况
        int left = 0, right = nums.size()-1,ans= -1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] >= target){
                right = mid-1;
            }else {
                ans = mid;
                left = mid+1;
            }
        }
        return ans;
    }

可以发现，把这四个函数，按照 力扣34题 题意去组合，都可以通过。