有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;
......
阅读全文