LeetCode 81. 搜索旋转排序数组 II

1

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int index = -1;
        for (int i = 0; i < nums.size() - 1; ++i){
            if (nums[i] > nums[i + 1]) index = i;
        }
        if (index == -1){
            index = nums.size() - 1;
        }
        return binarySearch(nums,target,-1,index) || binarySearch(nums,target,index,nums.size() - 1);

    }
    bool binarySearch(vector<int>& nums,int target,int l,int r){
        //左开右闭
        while (l < r){
            int mid = l + ((r - l) >> 1) + 1;
            if (nums[mid] < target){
                l = mid;
            }else if (nums[mid] > target){
                r = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};

2

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        //左闭右闭
        int start = 0;
        int end = nums.size()-1;
        while (start <= end){
            int mid = start + ((end - start) >> 1);
            if (nums[mid] == target) return true;
            if (nums[mid] == nums[start]) start++;
            else if (nums[mid] >= nums[start]){  
                //左区间增序
                if (nums[mid] > target && target >= nums[start]){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }else{
                //右区间增序
                if (nums[end] >= target && target > nums[mid]){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }
        }
        return false;
    }
};