有duplicate的确会有影响，最坏情况下复杂度为O(n)。
产生影响的例子
(1)5,5,5,5,9,5
(2)5,9,5,5,5,5
这种情况下没有办法知道该如何二分。只能简单枚举了，两种枚举办法：
(1)枚举最左端(l++) 或者最右端(r--)
(2)我这里的策略比较暴力，当没法二分时候，我直接从左到右遍历一边，看看target在不在。
public class Solution {
public boolean search(int[] A, int target) {
int l, r, m;
l = 0;
r = A.length - 1;
while (l <= r) {
m = (l + r) >> 1;
if (A[m] == target)
return true;
else if(A[l] < A[m]){
if(target >= A[l] && target < A[m])
r = m - 1;
else
l = m + 1;
}
else if(A[l] > A[m])
{
if(target > A[m] && target <= A[r])
l = m + 1;
else
r = m - 1;
}
else if(A[m] == A[l] && A[m] != A[r])
{
l = m + 1;
}
else
{
for(int i = l;i<=r;i++)
if(A[i] == target)
return true;
return false;
}
}
return false;
}
public static void main(String[] args){
Solution sol = new Solution();
int[] A = new int[]{1,1,3,1};
System.out.println(sol.search(A, 3));
}
}