LeetCode 81.Search in Rotated Sorted Array II (搜索旋转排序数组 II)

朱雀 2022-05-10 09:58 241阅读 0赞

题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 `[0,0,1,2,2,5,6]` 可能变为 `[2,5,6,0,0,1,2]` )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 `true`，否则返回 `false`。

**示例 1:**

输入: nums = [2,5,6,0,0,1,2], target = 0
    输出: true

**示例 2:**

输入: nums = [2,5,6,0,0,1,2], target = 3
    输出: false

**进阶:**

*  这是 [搜索旋转排序数组][Link 1] 的延伸题目，本题中的 nums 可能包含重复元素。
 *  这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

AC C++ Solution:

class Solution {
    public:
        bool search(vector<int>& nums, int target) {
            int left = 0, right =  nums.size()-1, mid;
            
            while(left<=right)
            {
                mid = (left + right) >> 1;
                if(nums[mid] == target) return true;
    
                // the only difference from the first one, trickly case, just updat left and right
                if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;}
    
                else if(nums[left] <= nums[mid])
                {
                    if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1;
                    else left = mid + 1; 
                }
                else
                {
                    if((nums[mid] < target) &&  (nums[right] >= target) ) left = mid+1;
                    else right = mid-1;
                }
            }
            return false;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/