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[l] <= A[m]在数组中有重复元素时无法保证[l,m]是sorted

当输入：[1,3,1,1,1], 3

这里参考：

分为两种情形：

1. A[l] < A[m] 则[l, m]是递增的

2. A[l] = A[m] 此时是重复元素，无法确认哪一部分是有序的，则跳过l，l++

1 public class Solution { 2     public boolean search(int[] A, int target) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         int len = A.length; 6          7         // binary search 8         int l = 0; 9         int r = len - 1;10         while(l <= r){11             int m = (l + r) / 2;12             if(target == A[m])13                 return true;14             15             // lower is sorted16             if(A[l] < A[m]){17                 if(A[l] <= target && target < A[m])18                     r = m - 1;19                 else{20                     l = m + 1;21                 }22             } else if(A[l] > A[m]) {23                 // upper is sorted24                 if(A[m] < target && target <= A[r]){25                     l = m + 1;26                 } else{27                     r = m - 1;28                 }29             } else {30                 l = l + 1;31             }32         }33         return false;34     }35 }

 

ref: