Leetcode|二分+缩小左右区间去重|81. 搜索旋转排序数组 II

SL_World

发布于 2022-01-10 15:12:47

2080

发布于 2022-01-10 15:12:47

文章被收录于专栏：XX

1 二分+缩小左右区间去重

对于nums[left] == nums[mid] == nums[right]情况，如nums=[3,1,2,3,3,3,3]， target=2 nums[0] == nums[3] == nums[6] == 3，无法判断该搜索左侧区域还是右侧区域，一个简单的想法是同时缩小左右侧区域

[left, right] => [left + 1, right - 1]
nums=[3,1,2,3,3,3,3] => nums=[1,2,3,3,3]

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int size = nums.size();
        int left = 0, right = size - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return true;
            // 关键：对于重复元素nums[left] = nums[mid] = nums[right]难以判断target在哪个区间
            // 那就缩小[left, right]区间，即left++; right--;
            else if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
                left++; 
                right--;
            } else if (target < nums[mid]) {
                if (nums[left] > nums[mid] || (nums[left] < nums[mid] && target >= nums[left]))
                    right = mid - 1;
                else left = mid + 1;
            } else if (target > nums[mid]) {
                if (nums[mid] > nums[right] || (nums[mid] < nums[right] && target <= nums[right]))
                    left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
};