81. Search in Rotated Sorted Array II.md

81. Search in Rotated Sorted Array II

思路

在一个经过了循环移位的有序数组（可能有重复元素）里进行查找，在有序数组里进行查找，肯定二分。
这题和33. Search in Rotated Sorted Array其实是类似的，唯一不同就是此题可能有重复元素。 但是基本思路不变，参考33题题解思路二， 我们得到一个重要的想法：二分后左右两半至少有一半是有序的。所以我们可以判断target是否在这有序的一半，若在则丢弃掉另一半进入下一次循环，若不在则丢弃掉有序的这一半进入下一次循环。 那么如何判断哪一半是有序的呢?分为以下几种情况：

1. 若nums[mid] == target，则返回true即可。
2. 若nums[low] < nums[mid]，则左半边一定有序；
3. 若nums[low] > nums[mid]，则右半边一定有序；
4. 否则，我们无法判断到底哪一边有序，但是可以肯定的是nums[low] != target，所以此时我们直接low++然后进入下一循环。

最坏的情况就是数组中元素全相等且不等于target，此时时间复杂度为O(n)
空间复杂度O(1)

C++

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