# Search in Rotated Sorted Array II

### 描述​

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

### 分析​

• A[left] < A[mid]，则区间[left,mid]一定递增
• A[left] == A[mid] 确定不了，那就left++，往下看一步即可。

### 代码​

// Search in Rotated Sorted Array II// Time Complexity: O(n)，Space Complexity: O(1)public class Solution {    public boolean search(int[] nums, int target) {        int first = 0, last = nums.length;        while (first != last) {            final int mid = first  + (last - first) / 2;            if (nums[mid] == target)                return true;            if (nums[first] < nums[mid]) {                if (nums[first] <= target && target < nums[mid])                    last = mid;                else                    first = mid + 1;            } else if (nums[first] > nums[mid]) {                if (nums[mid] < target && target <= nums[last-1])                    first = mid + 1;                else                    last = mid;            } else                //skip duplicate one                first++;        }        return false;    }};