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.

Analysis

• 多加一种nums[mid]==nums[low]的情况。 这种情况下无法判断左边还是右边是sorted的。这时把low++，一步一步靠近。

Code

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums==null || nums.length==0) {return false;}

       int low = 0;
       int high = nums.length-1;//这里high用len-1而不是len是因为下面需要比较target和nums[high]的大小,nums[high]要有意义

       while (low +1 < high){ 

           int mid = low + (high-low)/2;

           if (target == nums[mid]) {return true;}

           if (nums[mid]>nums[low]){//1st half is sorted
               if (target > nums[mid]) {low = mid;}
               else {
                   if (target == nums[low]) {return true;}
                   else if (target > nums[low]) {high = mid;}
                   else {low = mid;}
               }
           }
           else if (nums[mid] < nums[low]){//2nd half is sorted
               if (target < nums[mid]) {high = mid;}
               else {
                   if (target == nums[high]) {return true;}
                   else if (target >nums[high]) {high = mid;}
                   else {low = mid;}
               }
           }
           else {
                low++;
           }
       }

       if (nums[low]==target || nums[high]==target) {return true;}

       return false;
    }
}

Reference

Leetcode