声明: 以下描述并非抱怨，而只是针对面试中的算法题，希望给别人提供点借鉴，更多地清醒头脑，理清思路，跳出当时的思维局限，和面试官互动解决掉面试题。
本人技术背景: 全栈式Ruby on Rails开发四年多，并在大数据分析方面有些经验，详见个人主页 http://mvj3.github.io 。
今天面试的时候被要求手写二分查找代码。
这让我不由得想起几年前去yottaa面试要求手写二分查找代码时失败的窘迫来。于是我和面试官提了说，有人说过 专业程序员里的90%都无法正确实现二分查找 ，而且我之前用 二分查找实现过日志二分查找 ，大概原理就是不断依据范围进行折半查找。面试官还是要求现场写一个，于是我只好硬着头皮开始写了，不断回想和思考里面的边界和技巧，脑子里一团乱，在纸上写实在没感觉（因为要运行程序测试嘛，本人的大脑还不是CPU。。。），就打开自己带的笔记本开始写了。
测试代码是：
puts binary_search((1..15).to_a, 8) == 7
puts binary_search((1..15).to_a, 1) == 0
puts binary_search((1..15).to_a, 14) == 13
puts binary_search([2,3,8,15], 8) == 2这个没有疑问。然后先写了代码的轮廓，因为之前项目有好多模块都是通过递归实现的，就构造了一下 binary_search array, value, from, to 这样的API，最终代码是：
def binary_search array, value, from = nil, to = nil
return nil if array.blank?
from ||= 0
to ||= array.size
mid_idx = ((from + to) / 2.0).round
mid_val = array[mid_idx]
if value == mid_val
return mid_idx
elsif value > mid_val
binary_search array, value, (mid_idx+1), to
else
binary_search array, value, from, (mid_idx-1)
end
end测试通过。面试官反应用迭代方式实现，他说有性能问题。这里稍微和他有些讨论，迭代就迭代吧，我和他说那就用这第二种方式实现。
这次写的时间比较久，估计在二三十分钟，遇到死循环的问题。途中和面试官抱怨了一句，他回说就是考边界。最终调试无果（当时我严重怀疑是边界出了问题，但是我想不起那个准确的解法），就说和面试官一起看看吧。
def binary_search array, value
@idx = nil
loop do
@from ||= 0
@to ||= (array.size - 1)
return nil if array[@from..@to].blank?
puts "+ #{@from + @to}"
@idx = ((@from + @to) / 2.0).round
puts "[#{@from}, #{@to}] #{@idx}"
#binding.pry
mid_val = array[@idx]
if value == mid_val
break
elsif value > mid_val
@from = @idx.round
break if value == array[((@from + @to) / 2.0).round]
else
@to = @idx.round
break if value == array[((@from + @to) / 2.0).ceil]
end
end
return @idx
end上面在跑前二个用例是准确的，但是第三个有点异常了，现在回来一看才发现是实例变量在方法多次调用后混淆的问题。而其中出现round和ceil之类方法的原因是他和我提到了之前远程面试时做的一个题目里我没有用 String#chars 这样更Ruby的写法，而是用了 str.split(//) ，所以我潜意识里可能顺着他的这个原则走了，当然这里的路走错了。
下面的是我现在改好的：
def binary_search array, value
puts "查找数组 #{array}, 值 #{value}" if ENV["DEBUG"]
from, to, idx = 0, array.size.pred, nil
loop do
return nil if array[from..to].blank?
idx = (from + to) / 2
mid_val = array[idx]
puts "起始 #{from}, 终止 #{to}, 当前索引 #{idx}" if ENV["DEBUG"]
if value == mid_val
break
elsif value > mid_val
from = idx + 1
else
to = idx - 1
end
end
return idx
end在和他讨论这个迭代的死循环代码时，他指明写的太冗余了，好的写法应该可以更短。这个就突然提示了我想起以前其实在yottaa面试结束后回家就调查了相关资料，然后写过 这两个版本 的，里面还包括插入功能，更深的影响就是加入eoe后写了上面提到的logpos日志二分查找模块。
然后我打开以前保存的代码，给他看，他反馈说还是可以更短。我说能不能找给我看。他说你回去可以自己找。
现在回来搜了一个迭代版本的， http://gistflow.com/posts/199-binary-search-with-ruby-and-tdd
class Array
def iterative_bindex element, lower = 0, upper = length - 1
while upper >= lower
mid = (upper + lower) / 2
if self[mid] < element
lower = mid + 1
elsif self[mid] > element
upper = mid - 1
else
return mid
end
end
return nil
end
end按语义来说，包括关键字和方法， %W[class Array def iterative_bindex element lower = 0 upper = length - 1 while upper >= lower mid = () upper + lower / 2 if self[] mid < element lower = mid + 1 elsif self [] mid > element upper = mid - 1 else return mid end end return nil end end] ，为55个词。
而我回来后实现的版本， %W[def binary_search array value from to idx = 0 array size pred nil loop do return nil if array [] from .. to blank? idx = () from + to / 2 mid_val = array [] idx if value == mid_val break elsif value > mid_val from = idx + 1 else to = idx - 1 end end return idx end] 为62个词。
我个人觉得两者无甚区别。不知道哪位大牛可以给出更短的Ruby版本，标准算40个词吧。
最后面试官总结我应用或Rails方面的经验比较多，但是算法不太行，他准备和CEO再讨论看看。于是我咨询他公司技术部有哪些算法工作，他提了一个数据排重，然后我说如果准确度不太要求的话，可以用bloomfilter进行过滤。但是他坚持这一轮面试结束了，于是只能出门和他道别了。
额，只能等后续再沟通了，总之有点冤。。。
本人之前写过 前端工程师的面试也可以如此生动 ，过段时间也总结一篇如何面试Ruby工程师的文章吧。
Ruby默认实现为什么是遍历查找的？慢啊。