7
回答
一道面试题,自己写的不严谨
华为云实践训练营,热门技术免费实践!>>>   

一个递增数列,要求用折半查找的方法找出 b 所在的下表

int find(int[] a, int b){

.......

}

 

举报
luger
发帖于5年前 7回/505阅
共有7个答案 最后回答: 5年前
这个题已经很明确了吧,直接二分查找,和b比一下,时间复杂度是log n.
--- 共有 1 条评论 ---
luger那请你写一个 不能调试看结果七分钟之内写完 我写出来了 但是不严谨 有的情况没考虑到 5年前 回复
你应该面试不通过,这种题目你居然自己不能独立写
--- 共有 1 条评论 ---
luger那请你写一个 不能调试看结果七分钟之内写完 我写出来了 但是不严谨 有的情况没考虑到 5年前 回复
  int find(int[] a , int start , int end,int b)  {

    int mid = (start + end) /2;

    if(b == a[mid])

        return mid;

    else if( b <a[mid])

        return find (a,start,mid,b)

    else

       return  find(a,mid+1,end,b);

}

--- 共有 1 条评论 ---
lugerfind(int[] a, int b) 不能设其他参数 5年前 回复
一个完美的折半确实需要考虑的比较全~ 另外楼上上的方法连不存在都没有考虑。。。
--- 共有 2 条评论 ---
俏文安对的,忘了b不在a里面的情况。 5年前 回复
luger恩恩 知道了 谢谢 以后会注意的 5年前 回复

我相信起码一半以上的人没法在10分钟之内写出正确的二分查找(至少我面试过的人都没戏)

另外LZ你的代码最好提前判断查找值与边界直接的关系,直接返回-1

稍微改了改:

    static int find(int[] a, int b) {
        int lowerBound = 0;
        int upperBound = a.length - 1;
        if (a[lowerBound] > b) {
            return -1;
        }
        if (a[upperBound] < b) {
            return -1;
        }
        while (lowerBound <= upperBound) {
            int curIn = (lowerBound + upperBound) / 2;
            if (a[curIn] == b) {
                return curIn;
            } else if (a[curIn] < b) {
                lowerBound = curIn + 1;
            } else {
                upperBound = curIn - 1;
            }
        }
        return -1;
    }

--- 共有 2 条评论 ---
醪糟儿蛋回复 @xinzaibing : 楼主的标签是java,再者 c/c++ 有int []a 这种写法吗? 5年前 回复
xinzaibing在C\C++ 中数组有:a.length 这种用法吗...? 专业一点啊.... 5年前 回复
顶部