注：数组是有序的，和面试官确认过。方法签名是 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)
#8 楼 @arth 首先变量名，是不是看谭（浩强）哥的书学得编程？变量名最好起个有意义的，这样一看就明白了。这是谭哥的书唯一被吐槽的。 其次，问题出在了
int m=p+(r-p)/2;
这句。 因为 m, r, p 都是 int 型的， 所以当如果 p=2,r=3 时，m = p + 0, 所以程序陷入死循环。
最后，代码的风格也很重要。每种语言都有一套社区推荐的格式规范，建议学习一下。
贴一段大神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 <[email protected]> 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