这道题是二分查找Search Insert Position的变体,思路并不复杂,就是先用二分查找找到其中一个target,然后再往左右找到target的边缘。找边缘的方法跟二分查找仍然是一样的,只是切半的条件变成相等,或者不等(往左边找则是小于,往右边找则是大于)。这样下来总共进行了三次二分查找,所以算法的时间复杂度仍是O(logn),空间复杂度是O(1)。 代码如下:
public int[] searchRange(int[] A, int target) { int[] res = new int[2]; res[0] = -1; res[1] = -1; if(A==null || A.length==0) { return res; } int l=0; int r=A.length-1; int m=(l+r)/2; while(l<=r) { m=(l+r)/2; if(A[m]==target) { res[0]=m; res[1]=m; break; } else if(A[m]>target) { r = m-1; } else { l = m+1; } } if(A[m]!=target) return res; int newL = m; int newR = A.length-1; while(newL<=newR) { int newM=(newL+newR)/2; if(A[newM]==target) { newL = newM+1; } else { newR = newM-1; } } res[1]=newR; newL = 0; newR = m; while(newL<=newR) { int newM=(newL+newR)/2; if(A[newM]==target) { newR = newM-1; } else { newL = newM+1; } } res[0]=newL; return res; }实现中用到了在Search Insert Position中提到的方法,可以保证当搜索结束时,l和r所停的位置正好是目标数的后面和前面。
有朋友在留言中提到这里可以只用两次二分查找就足够了,确实如此。 如果我们不寻找那个元素先,而是直接相等的时候也向一个方向继续夹逼,如果向右夹逼,最后就会停在右边界,而向左夹逼则会停在左边界,如此用停下来的两个边界就可以知道结果了,只需要两次二分查找。代码如下:
public int[] searchRange(int[] A, int target) { int[] res = {-1,-1}; if(A==null || A.length==0) { return res; } int ll = 0; int lr = A.length-1; while(ll<=lr) { int m = (ll+lr)/2; if(A[m]<target) { ll = m+1; } else { lr = m-1; } } int rl = 0; int rr = A.length-1; while(rl<=rr) { int m = (rl+rr)/2; if(A[m]<=target) { rl = m+1; } else { rr = m-1; } } if(ll<=rr) { res[0] = ll; res[1] = rr; } return res; }二分查找的题目还是比较常考的,既带有一点算法思想,实现上也不会过于复杂,很适合作为面试题,类似的题目还有Search in Rotated Sorted Array。
你好。请教个问题,如果 输入A={8,8,8,8,8,8},那么worst cast 是不是O(n) 啊? 谢谢。
回复删除这里还是O(logn)的,因为找到一个8之后,他对左边和右边还是进行二分查找,所以不会一个个找的。只是这里元素太少,你感觉不出来logn的优势,你可以用更大的规模(比如50个8)就能看出来了哈~
删除明白了。你的code 的确是O(logn), 我之前算法平均时间是O(logn), worst case 就是O(n) 了。。。。。 谢谢 ^_^
删除