Duder's Blog

总结一下这几天遇到的二分方法解决问题

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

题目描述

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

题解

二分法，左值右值分开判断

自己写二分法
先二分法找到重复数的左值，再二分法找到重复数的右值
判断条件
当大于等于中间点，右值继续缩进，直到相遇返回左值；
当小于等于中间点，左值继续缩进，直到相遇返回右值；
最后计算 右值-左值+1

class Solution {
public:
    int binarySearchLeft(vector<int>& nums, int target) {
        int left = 0;
        int right = (int)nums.size()-1;
        int ans = (int)nums.size();

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

        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]>target){
                right = mid - 1;
            }else{
                left = mid + 1;
                ans = mid;
            }
        }
        return ans;
    }

    int search(vector<int>& nums,int target){
        int leftIdx = binarySearchLeft(nums,target);
        int rightIdx = binarySearchRight(nums,target);
        if(leftIdx <= rightIdx && rightIdx < nums.size() 
        && nums[leftIdx] == target && nums[rightIdx] == target){
            return rightIdx-leftIdx+1;
        }
        return 0;
    }
};

官方题解给出一个很有意思的方法，通过lower的方式控制判断条件的等号，从而实现左值右值的寻找在一个函数实现

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

    int search(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-wl6kr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

看到的一个STL调包的二分

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return upper_bound(begin(nums), end(nums), target) - lower_bound(begin(nums), end(nums), target);
    }
};

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

题目描述

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

题解

二分法，有序排列
注意边界条件[0] —— 1，[1]——0
最后返回时判断，如果为初始位置，说明缺值在末尾。
时间复杂度O(logn)，空间复杂度O(1)

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

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

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

题解

可以使用暴力解遍历，这里使用二分法实现
主要是重复点的判断标准，当中间点与右值相等时，逐步移动右值，防止出现极小点。
该方法使用左值返回，因此需注意返回值使用

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size()-1;
        while(low<high){
            int mid = (low + high)/2;
            if(numbers[mid] < numbers[high]){
                high = mid;
            }
            else if(numbers[mid]>numbers[high]){
                low = mid+1;
            }
            else{
                high-=1;
            }
        }
        return numbers[low];
    }
};