求职 面试时候如何用 Ruby 写一个最短二分查找代码
声明：以下描述并非抱怨，而只是针对面试中的算法题，希望给别人提供点借鉴，更多地清醒头脑，理清思路，跳出当时的思维局限，和面试官互动解决掉面试题。
本人技术背景：全栈式 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 工程师的文章吧。
#1 楼 @goinaction 这应该是面实际 coding 能力。二分法大家都清楚的。来一个快排估计会筛掉 95% 的人，ruby 人本来就少筛筛就没有了。。
#1 楼 @goinaction 从单独给这道题和我问的算法业务还真没看出来，就大部分应用层的 Rails 系统而言，真的不需要应用什么算法，当然这也不是说算法就不需要了解和掌握，它对你架构系统有好处。如果写一些底层库，可能需要那么一些算法，但是很多开源都有，而且也只是作为一个模块引入即可，所以应用层的开发人员只需要了解原理即可。
#2 楼 @linjunhalida "手写二分查找代码"难度其实挺高的，在同样了解基本算法原理条件下，除非面试者提前背书，否则写的代码真的有 BUG。二分查找算法"虽然早在 1946 年就有人将二分查找的方法公诸于世，但直到 1962 年才有人写出没有 bug 的二分查找程序。"，我觉得我们论坛大部分人都比不过那些大牛吧，何况也没人发明个厉害的基础算法出来，所以面试中的大部分实现我可以说就是和高考一样的性质，背书而已。
本人不是算法大牛，智商也只是够考个三本学校而已，了解的常用算法最高层次也只有二分查找和 B-Tree 等相对直观的概念而已，其他高级的红黑树，优先队列等数据结构我可能就得花一点时间去明白其中过程。
但是这不妨碍我写诸多 Ruby 相关开源软件 和 统计分析引擎框架 statlysis 。就个人直观的理解，常用算法无非就是 CPU 和 IO 互换，或者发现里面某些规律，比如以下几种（数据挖掘和机器学习等排除）
- 各种树，无非是针对查找，删除，插入等组合优化。
- 各种排序，里面包含各种二分，三分，广度优先，深度优先等思想。
- 散列，只要知道映射原理就可以了，如果对 IO 有要求的，可以适当降低精度。
- 图论，这个 Web 开发一般还真用不到，我唯一用过的是 依赖排序 。
- 动态规划简单的就是理解为 Rails 里的各种组合和缓存嘛，哈夫曼编码也就是排个序映射一下而已，等等。
以上可能有错误，望算法大牛指点！我分析的关键点是上面的都太数学了，是给 Knuth 等搞数学的人玩的，给那些写数据库，操作系统，网络等的大牛们玩的。
而对于像我这样的类似 DHH 一样容易数学不及格的人直观的理解这些算法即可，也许我们更懂得直观的如何像作一幅油画一样把一个大型程序写好并模块化，依我看 Web 开发大牛 @huacnlee 也是属于这种人。
举个 Python 的例子，假如我面试某人，出了一个需要使用二分查找的题
知道二分查找的基本原理，但写不出正确程序的给 D 写出正确程序但是性能不是最优的给 C 写出正确的二分查找实现的给 B 用 bisect 标准库的给 A
说我需要搜搜 Google 看看 Python 有没有二分查找的库/实现的也给 A，真的
第 2466 位会员
ID: rasefon
Name: Raw
城市: 上海市
公司: Autodesk
Email: [email protected]
Since: 2012年6月08日
倍受大家喜欢的帖子
Ruby 发个很好的 Ruby VM 的学习资料 13 人喜欢, 9 条回复
数学 傅立叶变化的完美解释。 5 人喜欢, 6 条回复
算法 相似图比较算法。 2 人喜欢, 2 条回复
瞎扯淡 恒大威武！！！ 0 人喜欢, 39 条回复
瞎扯淡 关于 C++，关于 gc 的一些东西 0 人喜欢, 24 条回复
瞎扯淡 分享一首非常赞的歌和歌词。 0 人喜欢, 1 条回复
Ruby 无意中找了 ruby 语法的伪 BNF 范式，发出来给大家参考一下。 0 人喜欢, 4 条回复
Ruby 2.0 respond_to?(x,x) 坑死人！ 0 人喜欢, 4 条回复
瞎扯淡 最近想到一个关于上传图片的问题。 0 人喜欢, 8 条回复
Gem Ubuntu 下国内的 gem 镜像有问题。
对于这种以关注 VM, 傅里叶，相似图，BNF 范式的人去写二分查找，红黑树，AVL 树等数据结构为兴趣的人，本人表示不需要解释。
#17 楼 @rasefon 但是我反对面试时过多的考察这种单向编码的笔试，而是应该结合业务来互动为主，当然这个得要求面试官有足够的驾驭能力。
我最讨厌压力编码了，这就是变相的加班，把工程师当码农使。写程序其实是个创造性的过程，只有艺术家自己才能给自己压力，外在的压力只会导致堆砌垃圾冗余问题代码。
#18 楼 @camel 写和理解是两回事（我个人觉得最重要的是结合业务能深入的理解），做学术写的代码和做工程写的代码也是两回事。这种只占软件工程里一小部分的算法，我觉得没必要拿出来太当回事。
请问你写过的软件中有多少是需要你手工实现这种基础算法的，如果简单或有很强的应用，那为何我们写 Ruby 的基本就用不到呢，而是直接放到 Array#binary_search 就可以了呢。编写常用排序算法，也就是对不会实际工程的刚毕业的学生练练得了。
#21 楼 @rasefon 算法它的确也是实用的能力，但它只是数学模型，而不是工程模型。因为算法只是从工程中提炼，就像你不会因为 MongoDB 用了 B-Tree 而去为它买单，而是为它提供了良好的工程而买单。所以我以为用人单位对待面试者也应该如此。
对于你举例的"业务逻辑密集型软件，比如各种 ui，金融软件等"，如果你觉得它们只是单纯的体力劳动，我不赞同，只能说明你的经验太浅了，我以为两者兼备，而且智力投入更重要，这个从国内外网站的质量就可以看出来。国内对开源软件贡献的太少，而国外的开源遍地开花。国内的只会死板的逻辑性分析开源软件，最多打个补丁，而国外更多在于创造解决方案。
所以对于成熟的软件工程师，比如三四年以上，我以为看 TA 如何解构分析 TA 之前做过的项目更为有益，或者就面试公司的实际工程问题，去考察面试者的经验和思路，以及迭代过程。
#19 楼 @mvj3 面试中之所以重视算法，我感觉是因为：
算法是短期内测试一个人抽象思维和学习能力虽不完美，但最高效的方法 个人非常赞成这种做法。
算法与语言，我觉得后者是软实力，前者是硬实力。
如果要招人救火，写一两年 Ruby 后走人，就招相对熟悉 Ruby 的。 如果要招人一直做下去，并给团队带来新东西，那就招学习能力强的，培养新人的时间不需要很多。
我的团队里有个以前搞 Machine Learning 的，算法那是一套一套的，以前没写过 Ruby，但上来翻两本 Ruby 书就写的很溜，
我相信一个算法好的程序员能写好 Ruby，也能写好 Go，JavaScript....
这是一个有个最近很火的美帝前端面试活生生的例子 http://css-tricks.com/interviewing-front-end-engineer-san-francisco/ 前端面试没有问一个 HTML 相关，CSS 和 JS 只问一两个问题。 问的大多都是算法相关的问题。
事实本该如此
「黑客搞懂“计算理论”的必要性，与画家搞懂颜料化学成分的必要性差不多大，黑客新想法的最佳来源，并非那些名字里有“计算机”三个字的理论领域，而是来自于其解决问题的创作领域。」 我想 ruby 程序员更容易引起共鸣。
#36 楼 @rasefon 详见 为什么我反对纯算法面试题
看过这上面的分析，我相信你明白我为什么反对纯算法面试题了。原因就是纯算法的面试题根本不能反应一个程序的综合素质！
那么，在面试中，我们应该要考量程序员的那些综合素质呢？我以为有下面这些东西：
* 会不会做需求分析？怎么理解问题的？
* 解决问题的思路是什么？想法如何？
* 会不会对基础的算法和数据结构灵活运用？
另外，我们知道，对于软件开发来说，在工程上，难是的下面是这些挑战：
* 软件的维护成本远远大于软件的开发成本。
* 软件的质量变得越来越重要，所以，测试工作也变得越来越重要。
* 软件的需求总是在变的，软件的需求总是一点一点往上加的。
* 程序中大量的代码都是在处理一些错误的或是不正常的流程。
所以，对于编程能力上，我们应该主要考量程序员的如下能力：
* 设计是否满足对需求的理解，并可以应对可能出现的需求变化。
* 程序是否易读，易维护？
* 重构代码的能力如何？
* 会不会测试自己写好的程序？
所以，这段时间，我越来越倾向于问应聘者一些有业务意义的题，而且应增加或更改需求来看程序员的重构代码的能力，写完程序后，让应聘者设计测试案例。
比如：解析加减乘除表达式，字符串转数字，洗牌程序，口令生成器，通过ip地址找地点，英汉词典双向检索……
总之，我反对纯算法面试题！
以上是摘自该文章总结，我以为我在网上可见的 开源项目 都完全体现了上面所有要求，而这些都是来自我实际工程生涯中的长期结果，要算法有算法，要代码风格有代码风格，要需求分析有需求分析，要文档有文档，要重构有重构，就看面试官能否有水平 Hold 住。
好贴！我觉得无所谓对错，招聘方跟求职者处境类似，他想招到合适的人却不一定有发现分辨的能力。求职者即使有能力也不一定能说服招聘方。不能期待每次都遇到合格的面试官，对双方都是筛选的过程。 我个人认为能力有三个层面，我自己一直是这样去修炼。 算法与数据结构是基本功。所以人家要面试算法也无可非议。 二是解决实际问题的能力，主要是 OOA/OOD。有了 Rails/NodeJS 这样的工具，基本上可以想到哪写到哪，写代码不是主要问题，知道写什么才是问题。 三是搜索能力。当分析出问题所在，你可以就自己的知识范围给出解决方案，但更重要的是发现和利用别人的成果。其实是很难会遇到没有人解决过的问题了，github 上开源项目已经超过 100 万了，stackoverflow 上已经问过无数的问题了。如果真有前无古人的问题，那就是你做贡献的时候了。
更多的是，数据怎么表示都搞不清楚，就开始来瞎扯算法，协议大概需要有啥都没搞清楚，就开始来大谈架构，某个模型适用于哪些问题都没搞清楚，就在那里乱套 ...
但是很多面试非要考已经实现的算法的具体实现，真是很无奈啊 ...
对我这个算法盲来说，高深啊
return nil if array[from..to].blank?
blank 是 rails 的，ruby 语法没有滴 ^_^
之前公司来一小哥面试，聊了聊，他提到之前有做过导出 CSV，于是产生灵感，拿出之前帮同学解决过的问题： 一个上百页的有规则的 doc 文档，格式大概是
姓名：张三
公司：xxx
电话：11123
有少量数据错乱，比如
姓名：张三
公司：xxx
电话：11123
姓名：李四
公司：ooo
或者中文的冒号、英文的冒号混用
让他把这个文档转成 excel 能打开的表格，我和他结对完成，思路他完全提供，可以用任何手段，代码他有不会的地方我可以帮他写
我的想法是这样的：
- 了解他的背景，如果和我需要的不符，那开门见山好了
- 过去工作学习中积累了很多问题，结合面试者的背景和我需要招的岗位的能力，选择一个问题略做一些调整，交给他去完成
- 我会和他结对完成，可以观察他的思路、编码习惯，也可以在此过程相互分享经验
- 这样面试时间也不长，一个小时左右，我认为我对面试者有着充分的重视和尊重
这样面试如何？
我仔细看了 "这是一个有个最近很火的美帝前端面试活生生的例子 http://css-tricks.com/interviewing-front-end-engineer-san-francisco/ 前端面试没有问一个 HTML 相关，CSS 和 JS 只问一两个问题。 问的大多都是算法相关的问题。"，我想你理解的有点偏差了。。。这个正是他认为的反面例子。
他说算法是很重要，但是面试时候得结合实际的前端例子来，比如他举了
$("#nav a")
.addClass("link")
.attr("data-initialized", true)
.on("click", doSomething)
这样的例子来让面试者去解释这背后的原理和执行过程，这样才会让真正好的有经验的前端工程师被选中，他的原话是"The problem is they have nothing to do with front-end development. As I said before, most smart developers with a strong computer science background could answer all of these, even if they'd never built a website."
于是就有了这样的帖子……
貌似二分查找的应用场合不多，都排好序了，查找就没太多问题了，怎么查都快。考考 quicksort 才对。 不过那时候学的还有记忆，中间变量用的是 k，练下手
def binary_search(ary, num)
return -1 if num < ary.first or num > ary.last
k = ary.size / 2
i = 0
j = ary.size
while(i<=j)
if num > ary[k]
i = k+1
elsif num < ary[k]
j = k-1
else
return k
end
k = i + (j-i)/2;
end
-1
end
#59 楼 @rasefon 有一种叫数学竞赛，有一种叫数学创造，两种成分每个人都有，当然后者少多了，话语权只能被代表了。
但是当你去应聘一些相对高或者好的大公司的职位时，人家还是拿这种竞赛式的方式来搞，或者拿学历来卡人，而完全忽视了其过往项目经验在该专业能力上体现出来的创造力。遗憾的是有些人就是适应不了条件反射式的竞赛，TA 们更喜欢通过自省来创造，这方面工程实践可以看 Rails 项目 重构，我在阳光书屋的三个月 ，我对架构和 Model 的重构都是通过内在关系来自省解决的：）
把一个大家都很熟悉的、常用的算法拿过来实现一遍，这能够达到对算法能力进行评估的价值么？
我没有说只要会写常用算法就能通过面试，这种类似唐诗 300 首的算法是最初级的算法面试。 高级点做法应该是用算法解决问题。像：如何确定链表是否存在环，判断回文，你可以用任何语言实现。
他那个例子是自己 YY 的，在面试中不存在，所以没必要讨论。 他的想法肯定很多大牛想过，但最终大公司还是继续问算法（非语言框架），他们不是傻子。
不管你信不信，低级外包公司最不喜欢问算法问题，最喜欢问框架细节方面的东西。 刚毕业那会搞 Java，面试时都是问 Struts, Hibernate, Spring，如 Hibernate 某个配置项是什么意思。 还好我听到这些问题直接回去了。
低级码农拼的是记忆力，攻城狮拼的是想法，我还差的远。
#66 楼 @bhuztez B 大就别装嫩了
我知道的一种是用龟兔赛跑法http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
数据结构才学完查找与排序，不过我们是 JAVA 版的，还没用 ruby 来实现过。看到你的面试，个人觉得这方面知识现在应该学牢才行，尝试用不同的方法解决一个问题。
我面试的时候，算法问题可以通过思路考察，不一定要求写出完善的代码；但是肯定有写代码的考查题，也要考察思路、基本功、代码风格、习惯等等，其中最关健的还是找一些实际场景或者问题问一下候选人的思路，看看他会如何解决相关问题，并且是否能分析出该解决方案的优缺点和改进方向，顺便了解下沟通能力、表达能力、耐心等等，如果有不错的还会考察更多，比如团队合作、职业规划、文化适应性等，甚至有时候还是需要看看情商等，工程师也是需要有情商的。。。
def binary_search(ary, num)
ary.bsearch {|x| x >= num}
end
不知道还能怎么短了……
-
blank?是 rails 带来的方法吧？ - 没有 from 和 to 的边界判断，
puts binary_search((1..15).to_a, 16) == nil
哈哈，看 lz 的开源东西，是蛮牛的，可惜二分没写好。 我上次面试也写二分，还在纸上用笔写。。。写的时候那个紧张，那个＃￥%＃%￥%》。。。唉。。。呵呵，共勉。
#93 楼 @blackanger 到目前为止还没有人给出本质上更短的 Ruby 版本（参与此贴的算法大牛 @luikore 好像也没有看法） ，所以看来是那位面试官技术涵养有问题，他意思是你要背熟一个最短解法（二分算法解法在细节上还是可以是有很多不同的，我不相信谁在这么短时间里就这种原理性算法可以创造性地发明一个新解法，否则中国的计算机事业赶超美国就不用担心了），否则他看不明白，个人觉得他的水平只停留在王国维的第二层次。
#94 楼 @mahone3297 本人之前更有说服力的二分查找项目 logpos 被他忽视。。。一定得现场背出来一个。
要难倒一个人是很容易的，难的是如何去发掘别人的优点。
迭代版从递归略改下就可以了... 递归改循环的机械方法好像是算法有讲过的？而且这里是单递归，改成一个尾调用就很清楚了，都不用手动加栈。
def binary_search a, e, from=0, to=(a.size-1)
while to > from # if to > from
mid = (from + to) / 2 # mid = (from + to) / 2
case a[mid] <=> e # case a[mid] <=> e
when -1; from = mid # when -1; from = mid
when 1; to = mid # when 1; to = mid
else return mid # else return mid
end # end
end # binary_search a, e, from, to
# else
from # from
# end
end
#99 楼 @luikore #100 楼 @blackanger
国外都怎么面试比较高级的程序员呢，比如 CoffeeScript 作者，或者人家压根就不需要被面试？就是面试失败了，能就这样完全否定人家在这领域的价值吗？还是离职位要求或公司文化还有 1% 的距离？
个人觉得从过往项目，特别是开源的，再加上博客等这些被时间洗礼的网上公开信息，只要面试官洞察力和资历够深，比如 @luikore 这样的，还需要出题面试吗？我觉得详细地探讨下期待的将来能为公司作到哪些成绩或者贡献多大价值就可以了。
#102 楼 @blackanger 这个"综合考虑“确实可以灭掉很多人。不过我确实没看出了算法要求有多高，我以为好的算法面试应该是举实际例子，并在里面应用多个算法，而且过程中还是以原理性探讨为佳。编码习惯看面试者的开源项目就可以了。
好的 Web 开发人员是基础跟经验均衡，各方面水平平均，学习能力强的人。 尤其是 Full Stack 的开发人员。 水桶最短板理论最适合 Web 开发人员。
花大量的时间在调查一根木板是不是合格，其他木板花不花时间问呢。。 这种人才选拔制度值得怀疑。。
就好像买车。。 只看发动机。。 是不行的，
好的发动机还需要好的变速箱，真正吧发动机的力量传输到地面的还是轮胎跟轮圈。
动力好，开的舒不舒服，还要看好多其他的东西。。。
所有都一流的名车，说到最后还要看你买得起么。。
即便是名车也有法拉利，宾利，陆虎只分。。
这些名车也不是只用发动机来横向对比的。。
每个公司都有自己的风格，有缘有份的干着才舒服. 快速傅立叶变换，有需要的无偿奉送。
def fft(a)
n = a.size
return a if n == 1
w = Complex.polar(1, -2 * Math::PI / n)
a1 = fft((0 .. n / 2 - 1).map {|i| a[i] + a[i + n / 2] })
a2 = fft((0 .. n / 2 - 1).map {|i| (a[i] - a[i + n / 2]) * (w ** i) })
a1.zip(a2).flatten
end
输入 [2,4,2,8,9,2,6]) 输出 -9.117449009293669+3.9091574123401482i -3+0i -2.8825509907063323-3.9091574123401482i
觉得楼主第一个递归算法有点问题。二分查找应该有两个出口，一个是查找成功，这个出口再楼主代码中已经出现了。第二个出口是没有查找的数据，这个出口楼主没有。因为楼主代码中另一个出口是通过 array.blank？条件判断的。问题是递归过程中 array 没有变化啊。变化的只有 from 和 to。所以楼主要实现第二个出口，应该要判断 from 和 to 的关系。楼主试试 array 中没有的数据测试试试。应该有 bug
搜索搜到这个帖子，没啥事，就试着写了下，跑通那几个用例，一共用了不到 30 分钟。
感觉挺好写的。这个算法我知道怎么回事。翻译成代码就 ok 了，ruby 又这么好写。二分法的递归也是属于比较容易的递归。写个骨架，然后再加最简单的测试用例（下面的前 4 个），之后对着用例开始微调，无外乎就是加减 1 的问题，试几次就 ok 了。再之后，就看看给的测试用例有没用问题。
递归转遍历，只要理解递归的原理，把递归维护的状态，手动维护下，就 ok 了。反正测试用例有了，测试一直跑的，开始微调。
倒是觉得测试用例挺重要的。要是让我直接用面试官给的用例，我估计就要懵逼了。
递归是基本功。可以很好的锻炼抽象和分解问题的能力。递归学东西，一大片算法可以随便撸了。
递归可以这么考，先递归实现，之后用尾递归实现，再之后用遍历实现。再问问为啥尾递归可以被优化之类的。哈哈哈哈，我承认我挺无聊的。。。
代码如下，算法相关的，就没注意命名之类的问题。
## recursive version
def binary_search_helper(arr, ele, start, end_)
return false if start > end_
middle = (start + end_) / 2
middle_ele = arr[middle]
if ele > middle_ele
binary_search_helper(arr, ele, middle + 1, end_)
elsif ele < middle_ele
binary_search_helper(arr, ele, start, middle - 1)
else
middle
end
end
def binary_search(arr, ele)
end_ = arr.length
binary_search_helper(arr, ele, 0, end_ - 1)
end
def expect(r, expected)
unless r == expected
puts expected
else
puts "Success"
end
end
## iterative version
def binary_search_helper(arr, ele, left, right)
return false if left > right
while left <= right
middle = (left + right) / 2
middle_ele = arr[middle]
if ele > middle_ele
left, right = middle + 1, right
elsif ele < middle_ele
left, right = left, middle - 1
else
return middle
end
end
false
end
def binary_search(arr, ele)
length = arr.length
binary_search_helper(arr, ele, 0, length - 1)
end
expect binary_search([0], 0), 0
expect binary_search([0], 1), false
expect binary_search([0], -1), false
expect binary_search([], 0), false
expect binary_search((1..15).to_a, 8), 7
expect binary_search((1..15).to_a, 1), 0
expect binary_search((1..15).to_a, 14), 13
expect binary_search([2,3,8,15], 8), 2
