瞎扯淡 下面这个二分搜索有 Bug 吗?

arth · 2015年10月11日 · 最后由 arth 回复于 2015年10月21日 · 3345 次阅读

注: 数组是有序的,和面试官确认过。 方法签名是 int bbsearch(int[] sorted,int ta);也和面试官确认过。 前天面试某司,让写个二分查找,输入一个数组和目标值 ta,输出小于 ta 的最大值的下标(更新),没有则输出-1 。 这样的题目我做过很多了,很快就写出了如下版本(java)。然后发生了如下对话(回忆): 面: 你这个代码没问题吗? 我: 这里 r 表示不可达的右边界,可以简化判断。根据我做题的经验,感觉没有问题。 面: 如果 p=2,r=3,a[m]<ta, 你算法就有死循环了。 我: 这个应该不会,这样的条件应该不会发生。我再看看。 。。。。(肉眼 debug,此时面试官在看电脑). 大概三分钟后,我仍然没看出自己代码有什么问题。为了降低 bug, 我把 p=m 修改成了 p=m-1。 我: 我修改了一下, 这样应该不会死循环了。 面:...(略作思考) 我:这里要加个条件,防止 p<0。 面: 这题就到这里吧。

/** solution in java*/
public static int bbsearch(int[] a,int ta){
    int p=0;
    int r=a.length;
    while(p<r){
        int m=p+(r-p)/2;
        if(a[m]<ta){
            if(m+1==a.length ||a[m+1]>=ta)return m;
            p=m;    // 被修改的一行
        }else{
            r=m;
        }
    }
    return -1;
}

后来得知自己挂掉了,感觉很郁闷,这样的代码都能写错? 于是刚刚拿 ruby 改写了一遍。测试都通过了。 面试官提到的死循环,我感觉是不可能发生的。如果能达到他说的条件,那的确有可能死循环。但实际上无法满足那个条件,个人感觉。 无论有是面试措辞,还是程序,或者(能不能)达到死循环的用例,都希望能得到大家的提示。 求职心切, 先谢了。

# my ruby solution
def bbsearch(a,ta)
  return -1 if not a
  p,r=0,a.length
  while p<r
    m=(p+r)/2
    return m if a[m]<ta&&(m+1>=r || a[m+1]>=ta)
    a[m]<ta ? (p=m):(r=m)
  end
  -1
end
a=[1,2,3,7,9]
p bbsearch(a,3)
a=[1,1,2,2]
p bbsearch(a,3)
p bbsearch([2,2,2,2],3)
p bbsearch([2,2,2],3)
p bbsearch([0,1,2],3)

估计他没看到 a[m+1] 而且没听明白你说的话, 和面试官有关没办法

确定数组是有序的么?

#1 楼 @luikore 谢谢提示。如果下次碰到类似情形,该怎么和面试官沟通会好一点?

#2 楼 @SErHo 确认有序,刚修改了原文。 谢谢提醒。

个人觉得面试官在提出这个死循环的问题的时候,LZ 就应该详细解释这种情况会直接返回 m,一句 “我再看看” 暴漏了自己不自信呀。

#5 楼 @yuh 我当时告诉了面试官,这样的题自己做过很多次,应该不会有错。他提出的条件不会到达,所以不会发生死循环。但一来自己确实没找到关键点来反驳面试官,二来不想和面试官争执(那样感觉更没戏)。所以就说的再看看。 应该怎么说会好一点??

可能代码风格也有一点点问题吧, 比如操作符两边的空格, 变量名...

#7 楼 @krazy 当时是在纸上写的。 我这里的代码是用 vim 写的,没用 ide 的格式化。

#8 楼 @arth 首先变量名,是不是看谭(浩强)哥的书学得编程?变量名最好起个有意义的,这样一看就明白了。这是谭哥的书唯一被吐槽的。 其次,问题出在了

int m=p+(r-p)/2;

这句。 因为 m, r, p 都是 int 型的, 所以当如果 p=2,r=3 时, m = p + 0, 所以程序陷入死循环。

最后,代码的风格也很重要。每种语言都有一套社区推荐的格式规范,建议学习一下。 贴一段大神Paul Lutus的代码。 Paul Lutus

#!/usr/bin/ruby -w

# This script is (c) Copyright 2007, P. Lutus
# and is released under the GPL

# relaunch in window

exec("konsole -e #{$0} #{ARGV.join(' ')}") if ENV['TERM'] == "dumb"

# create m3u format playlists for each music directory

base="/netbackup/music" # change this path to suit your needs

albums = Dir["#{base}/*"]

albums.sort.each do |path|
   data = "#EXTM3U\n"
   # get the directory name, last element in path
   name = path.sub(/.*\/(.*)/,"\\1")
   name.gsub!(/_/," ")
   name.gsub!(/(\A|\s)\w/) { |c| c.upcase }
   puts name + " ..."
   tracks = Dir["#{path}/*.mp3"]
   tracks.sort.each do |track|
      track_name = track.sub(/.*\/(.*)/,"\\1")
      info =`mp3info -x #{track} 2>&1`
      info.sub!(/.*Length:\s*([\d|:]+).*/m,"\\1")
      m,s = info.split(":")
      secs = m.to_i * 60 + s.to_i
      data += "#EXTINF:#{secs},\n" + track_name + "\n"
      File.open("#{path}/#{name}.m3u","w") { |f| f.write data }
   end
end

print "Press Enter to close:"
STDIN.readline

#9 楼 @roclv 你说的条件并不可达。 变量名的话,数组用 a 似乎是可接受的惯例, 在很多算法书中,p 可以表示开头,r 表示结尾。m 表示中间。 在面试当时,ta 我写的是 target。昨晚将 target 写成 ta 这个习惯确实不好(主要是为了代码少,当时为了写完 target,A4 纸一行都写不下了。面试时在纸上写完整变量名会更有帮助吗? )。 这个给一个 java 的完整实现,可以发现 p2r3 时没有循环。

package algo;

/**
 * Created by ace <arthur4it@gmail.com> on 11, 10, 2015.
 */
public class BaiduSearch {
    public static int bbsearch(int[] a, int ta) {
        int p = 0;
        int r = a.length;
        while (p < r) {
            int m = p + (r - p) / 2;
            if (a[m] < ta) {
                if (m + 1 == a.length || a[m + 1] >= ta) return m;
                p = m;    // 被修改的一行
            } else {
                r = m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(bbsearch(new int[]{0, 1, 2, 4, 5, 6}, 3));
        System.out.println(bbsearch(new int[]{0, 1, 2}, 3));
        System.out.println(bbsearch(new int[]{2, 2, 2, 2}, 3));
        System.out.println(bbsearch(new int[]{0, 1, 2, 3}, 3));
    }
}

如果还是觉得有死循环的话,希望能给个能 fail 掉的用例。

#10 楼 @arth 如果我是面试官的话,我不仅会看你的代码,也会看你编程风格,包括但不限于变量名命名、格式规范等。 具体我没细看,估计面试官如果不是执行,而只是简单的浏览你的答案的话, 我猜你可能是这样被过滤掉的:

...
while (p < r) {
     // when p = 2, r = 3
      int m = p + (r - p) / 2;  //m = 2
       if (a[m] < ta) {
            //因为a[m] < ta(面试官设定),所以进入这里
            // 下面一行,有点复杂,直接掠过~
            if (m + 1 == a.length || a[m + 1] >= ta) return m;
             //p = m = 2 ,面试官觉得这陷入了死循环,事实上根据面试官给的设定,
             //因为m + 1 == 3, 已经在上一句返回m

              p = m;    // 被修改的一行
...

所以别气馁了 😄

He asks you to return the value, not the index. You should return a[m], not m.

This is my version:

def bsearch nums, val
  first = 0
  last = nums.size
  while first < last
    middle = (first + last) / 2
    if nums[middle] < val
      first = middle + 1
    else
      last = middle
    end
  end
  return -1 if first == 0
  nums[first - 1]
end

#12 楼 @emayej 如果是这样,返回-1 就是 bug.

#13 楼 @arth Why? Because the array may contains -1? You could raise that question during your interview.

#14 楼 @emayej That's the bug I found of yours, not mine. Anyhow, thank you for your idea. I will make the specs more clear.

#15 楼 @arth Then just return first - 1.

def bsearch nums, val
  first = 0
  last = nums.size
  while first < last
    middle = (first + last) / 2
    if nums[middle] < val
      first = middle + 1
    else
      last = middle
    end
  end
  first - 1
end

#16 楼 @emayej Your solution is better than previous now.

需要 登录 后方可回复, 如果你还没有账号请 注册新账号