LeetCode 81 Search in Rotated Sorted Array II

Posted on | In | 阅读

与leetcode 33有所不同，会存在重复出现数字的情况

  1. 在二分中若num[mid] == nums[left]就无法判断mid这个数落在右边的那段里还是左边的那段里，这时候只能先保守地left++然后进入下一轮
  2. 若num[mid] > num[left]，那么mid与left落在同一个单调段内，那么如果这时候target正好在num[mid] 与num[left]之间，那么可以很放心的把right移到mid-1的位置。否则可以将left移到mid+1的位置
  3. 若num[mid] < num[right]，情况与2相反。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.size() == 0){
            return false;
        }
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(nums[mid] == target) {
                return true;
            }else if(nums[mid] == nums[left]){
                left++;
                continue;
            }else if(nums[mid] > nums[left]){
                if(nums[left] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                if(nums[right] >= target && nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};