一道面试题,自己写的不严谨

luger 发布于 2012/08/18 09:36
阅读 510
收藏 0

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

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

.......

}

 

加载中
0
billzheng
billzheng
do you know there are www.baidu.com and www.google.com, so you can search!
十一文
十一文
正解!
0
俏文安
俏文安
这个题已经很明确了吧,直接二分查找,和b比一下,时间复杂度是log n.
luger
luger
那请你写一个 不能调试看结果七分钟之内写完 我写出来了 但是不严谨 有的情况没考虑到
0
挖粪涂墙
挖粪涂墙
你应该面试不通过,这种题目你居然自己不能独立写
luger
luger
那请你写一个 不能调试看结果七分钟之内写完 我写出来了 但是不严谨 有的情况没考虑到
0
俏文安
俏文安
  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);

}

luger
luger
find(int[] a, int b) 不能设其他参数
0
luger
luger
答案在我的博客 开始我用的递归 但是递归有很多情况需要判断 大家可以试试 回来后想了想 写了下面的  http://www.luger.me/archives/448.html
0
Jooooooker
Jooooooker
一个完美的折半确实需要考虑的比较全~ 另外楼上上的方法连不存在都没有考虑。。。
俏文安
俏文安
对的,忘了b不在a里面的情况。
luger
luger
恩恩 知道了 谢谢 以后会注意的
0
Jeky
Jeky

我相信起码一半以上的人没法在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;
    }

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