设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

Search for a Range -- LeetCode

2014-03-06 03:48:00.0 LeetCode leetcode java 面试 二分查找 search  
导读:原题链接: http://oj.leetcode.com/problems/search-for-a-range/ 这道题是二分查找Search Insert Position的变体,思路并不复杂,就是先用二分查找找到其中一个target,然后再往左右找到target的边缘。找边缘的方法跟二分查找仍然是一样的,只是切半的条件变成相等,或者不等(往左边找则是小于,往右边找则是大于)。这样下来总共进行...。。。
原题链接: http://oj.leetcode.com/problems/search-for-a-range/ 

这道题是二分查找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;}

有朋友在留言中提到这里可以只用两次二分查找就足够了,确实如此。 如果我们不寻找那个元素先,而是直接相等的时候也向一个方向继续夹逼,如果向右夹逼,最后就会停在右边界,而向左夹逼则会停在左边界,如此用停下来的两个边界就可以知道结果了,只需要两次二分查找。代码如下: 

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]

实现中用到了在Search Insert Position中提到的方法,可以保证当搜索结束时,l和r所停的位置正好是目标数的后面和前面。二分查找的题目还是比较常考的,既带有一点算法思想,实现上也不会过于复杂,很适合作为面试题,类似的题目还有Search in Rotated Sorted Array

(编辑: linhuanmars)

网友评论