*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.

解题思路：

This problem is similar to “Search in Rotated Sorted Array”. But there could be duplicates.

In problem “Search in Rotated Sorted Array”, we compare A[left] with A[mid] to determine which part does not contains the rotate pivot. But in this problem, A[left] could be equal to A[mid]. To solve this problem, we can let just add 1 to left when we face A[left] == A[mid] and continue the algorithm.

 1 public class Solution {
 2     public boolean search(int[] A, int target) {
 3         int start = 0;
 4         int end = A.length - 1;
 5         while (start <= end) {
 6             int mid = (start + end) / 2;
 7             if (A[mid] == target)
 8                 return true;
 9             if (A[start] < A[mid]) {
10                 if (target >= A[start] && target < A[mid])
11                     end = mid - 1;
12                 else
13                     start = mid + 1;
14             } else if (A[start] > A[mid]) {
15                 if (target > A[mid] && target <= A[end])  //注意边界条件
16                     start = mid + 1;
17                 else
18                     end = mid - 1;
19             } else
20                 start++;
21         }
22         return false;
23     }
24 }

Complexity

The worst case complexity will become

九章算法的模板解法：

 1 public class Solution {
 2     public boolean search(int[] nums, int target) 
 3     {
 4         if (nums==null||nums.length==0)
 5         return false;
 6         
 7         int start=0;
 8         int end=nums.length-1;
 9         
10         while(start+1<end)
11         {
12             int mid = (start+end)/2;
13             if(nums[start]>nums[mid])  //左边无序，右边有序
14             {
15                 if(target>nums[mid]&&target<=nums[end])start=mid;
16                 else end=mid;
17                 
18                 
19             }
20             else if (nums[start]<nums[mid]) //左边有序，右边无序
21             {
22                 if(target>=nums[start]&&target<nums[mid])end=mid;
23                 else start=mid;
24             }
25             else //nums[start]==nums[mid]
26             {
27                 start++;
28             }
29             
30         }
31         
32         if(nums[start]==target)return true;
33         if(nums[end]==target)return true;
34         return false;
35         
36     }
37 }