挖个坑，作为 python 程序员，面试时要求手写二分查找，可以说不么

之前去实习，给的题就有一道，花了好长时间才写对（而且是类似 Hack 的方法）瞬间感觉自己弱逼……

二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。

多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。如果你不认同这一点，最好的办法就是放下书本，自己动手写一写。试试吧。

我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间，可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。

我很惊讶：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。

我觉得二分查找应该算比较基础的算法~作为程序员，手写应该没难度吧~

吓得我立马去写了..

你问面试官要不比一比一行python解八皇后看谁先写出来？

二分又不复杂， 手写一下不算过份

你是来搞笑的么。python里面二分就不用手写了？

写个一般的不是随手的么，当然要没有bug可能要多想想啊

作为一个编程爱好者，百度了一下，终于知道了“什么是二分查找”……

其实我觉得我们这种非科班程序员……好吧，非科班编程爱好者来说，Glossary的确是个难点。

好多看起来高大上的名词一查百科就：“靠，原来不就是这个么。”

@binux 我觉得lz的开发可能不涉及到大量算法的东西，时间长了lz关注点就变了。

@lyragosa 难道非科班程序员就不用读书了么？

这应该算是基础了吧

太可怕了，现在这么水就敢去面试了么= =

@hahastudio 写得出来也不敢去面试 T,T

话说,如何提高自己信心?

就算不会写也该知道import bisect啊.

楼主是来反串黑python的吧..

这是最基本的算法，最近刚好在给人面试，自己想出来的一些题目，供大家参考：

1 走台阶问题：
很长的台阶，共有 X 级，一个大人每次可以走 m级 或者 n级，如果最后剩下不足 m级 或者 n级，那就算一步走完，问有几种不同的走法。
比如 7 级的台阶，每次可以走 2级 和 3级，有 5 种走法：
2->2->2->1
3->2->2
2->3->2
2->2->3
3->3->1

有两种解法： 1 动态规划 2 排列组合

2 能否求零问题：
给出一组正数，随意排列组合，每个正数使用且只使用一次，使用 +, - ，判断能否得到 0。
比如 {1,3,7,8,11} 那么 11 - 8 - 7 + 3 + 1 = 0。
而 {1,3,7} 那么无论怎么排列和+-都没办法得到 0。

解法：贪心求最优解

3 给出一组正数和目标值，判断能否在这组正数里每个数乘以一个非负数求和得到目标值。
比如 {3, 4} 目标值是 17，那么可以通过 3*3 + 2*4 = 17。
{3, 4} 目标值是 18，那么可以通过 6*3 + 0*4 = 18、 2*3 + 3*4 = 18 等等。
而如果 {9, 7} 目标值是 19，没办法找到合适的 非负数相乘求和 得到 19。

解法：这是一个 DFS 遍历的问题。

4 另外就是一些现实的问题，比如怎么简单实现一个 LRU cache。
解法：hash + 双向链表，能考一些编码细节。


这些题目虽然有些理论化，但是还是能看出编码能力的。

二分都写出来还好意思。。。。。都没问题快排，这都不肯写，给人的影响就是态度不好。。。

虽然我觉得楼主的“作为一个 Python 程序员”这个前提很奇怪，不过我疑惑的是，在很多地方类似这种“二分查找”或者“快速排序”之类的算法，真的有那么重要吗？实话说我没有遇到过需要自己写这种算法的场景啊，感觉真正用到这种算法的时候也有库可以解决问题啊，真的需要自己写的时候，找个库的代码来读，然后找些解释算法的逻辑的资料来读不就好了吗？

对于我们这种经常做业务软件开发的码农来说，算法确实已经是好遥远的事了= =
二分查找我还记得思路，写代码就不行了= =

楼上说简单的，自己先手写一遍试试呗~

某大牛说过“迭代者为人，递归者为神”

还是好好写吧。。。

@chuan 化递归为迭代的是什么 XD

@lyragosa 其实设计模式也是一样，随便看了几种原来都是早就在用的方法

我感觉快速排序堆排序等高级算法手写比较麻烦，二分啊冒泡啊这种肯定应该能手写出来的呀。

复习下 看看这个对不对

https://gist.github.com/anonymous/88614eca6b7e9e96cfba

@cloudzhou 第三题没说是否允许小数.....
因没给出限定条件,假定为可以.

最终答案就是: 因为任何数字都能满足要求,所以没有答案

另外,0不算是正数或者负数.....

说回来...
面试时候最怕给的空间不足还要手写.
给个windows记事本上机写都好....

这都写不出来，还是别当程序员了。

懂原理不难吧，之前面试还让手写快排

楼主想开点，我去面试前端，人家还叫我在白板上写遍历二叉树呢
思路一说就行，但是写出来真心烦啊

这个太简单了，不应该不会，懒的写也就算了，不会实在说不过去啊！

@mhycy 先得会这些基础的
遇到不会的先别一下子缴械投降了，先装一装
哪怕脑子真的一片空白呢，装作思考的样子= =
尽量往自己会的算法上套

实在不行了，可以试着把自己能做到的程度说一下，比如：
某一些特殊情况我能想到，可以这样这样做
中间有一些步骤我不太清楚，但是之前和之后的可以这样这样做

有人说不会手写快排我忍了，作为程序员你说你连二分都不会吗？

你应聘的职位是什么？如果是WEB方面的Python程序员，那会不会是无所谓的。

很多面试官应聘Web后端、手机客户端、Web前端都问跳出来问二叉树、红黑树、冒泡排序、快速排序之类的，不知道问来干嘛？
实际上也不难，找本书突击几天就没问题了，如果是Web方面的Python程序员，以后基本没用到这些的机会。

二分都不会 只会写helloworld？
还有一句话 talk is easy,give me code

@lincanbin 这些算法不常用。。。写一次就忘怎么破，面试前突击？

作为 Python 程序员，二分法都写不出来还打算理直气壮拒绝这也太那啥了吧

作为 Web 前后端，不会也就算了，但是人家愿不愿意接受还是个问题，其实花点时间做个题库也不难嘛

二叉还是很简单的嘛~~~

很可惜的告诉你们各种STL sort之后我是不会排序了的。。。。

基本上可以说明对方对你的定位低于你的期望.

手写二分不算啥吧

我觉得现在的情况是：最好不要再让面试者写这些大众题目了。因为有心的人会去准备，他们会把所有sort、所有基础数据结构相关的基础题目都去做一遍，记下来。这样就会出现面试不平等，考评内容对于一部分面试者来讲，是认真准备过的，这其实是不公平的。

当然，另一方面是：如果面试者真的把那么多内容都认真学习了，自身的水平确实也会提升很多。

我在想，我们是否可以这么来，我们准备一个高深一点偏一些的算法，然后准备好各种材料。让面试者现场学习，分析，然后现场写一些伪代码，或者代码实现一部分功能。在学习的时候面试官可以提供帮助。这不仅考察了大家关注的代码能力、思维能力，还考察了快速学习的能力（阅读文档，比如英文文档等），沟通能力（与面试官交流请教），抗压能力（算法本身较难）。再者，你可以提供电脑，让面试者可以进行Google等查阅资料。

快排也就两个 filter 加 list comprehension 的事情，所以还是用堆排吧。但其实堆排三五分钟也就写出来了。二分这么水不会不应该呀。

（不要让我等小学生产生哦我不用念书了我现在去应聘也能找到个 10k 的工作了的念头好嘛）

不过个人真的神烦二分查找，每次都要调试一两次才搞定。

二分要写的没有任何bug还是很考验人的。

int binart_search(int* array,int n,int k)
{
int i=0;
int j=n-1;
while(i<=j)
{
int mid=(i+j)/2;
if(array[mid]>k)
j=mid-1;
else if(array[mid]<k)
i=mid+1;
else
return mid;
}
return -1;
}

楼主愤怒有理, 面试考官没经验, 根本就是校招的路子.

没关系的，有次面试，我连32bit有符号数的表示范围都说错了，但不能说明我真的不会。

面试前稍微准备准备常用算法吧，什么样的面试官都有。

@lijsf (i+j)/2就错了……

这就是楼上说的，knuth说二分查找出来二十年才有没bug的代码……

某广告公司要求手写 排列组合
某头条要求30分钟内写没Bug的LRU
某乎要求时间O（1）的好友列表查询
某云公司要求当场8皇后
某浪要求用lambda 一行写逆排

楼主面的弱爆了

@JoeShu
这可是天然尾递归

反正我不会算法，我不配当程序员，我还是去种地吧

@freeze 就面试前突击咯，二叉树、红黑树、冒泡排序、快速排序等等，不合格的面试官一般只会考这些，常考的算法大概就10个。

二分不会写也能有15K，忽然觉得人生灰暗T_T

当年企鹅面试，隔壁的前端的房间在考他写kmp呢

如果问什么是二分法，会不会被打死？

@tioover
想起这个了， 直至06年 java 才修复了一个二分法的bug。

ref:
http://bugs.java.com/bugdatabase/view_bug.do?bug_id=5045582

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

楼主你确实可以换个公司面试了，没问题的

我碰到过考题是问 PHP 里的 $i++ 和 ++$i 的效率差别，但总共有好几十道题，直接略过了

我觉得一个很普遍的现象就是，见过很多公司招聘 Python / PHP 这种弱类型语言的程序员，但面试只爱考点算法、链表、指针之类的东西

很多面试官想的都是想的如何难道应聘者，下马威，有面子。而不是认真去想，如果找几个人分担我手里的活，我最关注他的哪些能力。我必问的一道题是 MySQL 复合索引的问题（其实这个只是很通用，比方说 MongoDB 里的索引跟 MySQL 里的就非常相近），如果能答个差不多说明他能自己规划表，而不需要我来花时间检查他的表设计是否正确。我不会告诉他，其实我tmd也不知道 B-Tree 是什么玩意

主要的还是职位需求，大多数职位只是普通的实现产品需求，而不是要参与做个新的 NoSQL 引擎或者搞点自然语言处理

@zhengkai

考一个二分不过分吧，至于 $i++ 和 ++$i 实在蛋疼。
了解算法的好处是能够快速分辨一个方案的好坏，你不一定要变成大厨，但是你至少要能分断出黑暗料理。

”这是道数学题，我给你解出来；这是段代码，我保证不了”。

楼上楼下各位的评论的语法和标点符号完全对吗？参考哪一年哪月哪天哪个机构多少人拟定到最后根据哪个版本定的哪个标准呢？至少应该不会造成歧义吧？

只有我认为考官是为了看思路和熟练程度而不关心最后结果吗

这些都是基本考题吧？实在不会随便编点想法也总比直接说不会的好

算了，我被LS的大神些吓得只想回去种地了

@JoeShu

35楼 @tioover 已经给出了
81楼 @skydiver 也是少有懂行的

好多人觉得“很不应该”的样子，楼主再问个如何用C写一个正确的int abs(int num)的函数，估计就被喷死了。

二分查找不很简单么？不过也极其讨厌在面试时要求手写代码。。

...虽然我挺久没写 Python 了……不过第一句显然应该是:

import bisect

@tioover 我去，当初面试的时候也被二分鄙视了，大家看来都是眼高手低

读完帖子我感觉原来v2ex有这么多会写二分查找的牛人啊!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
感概万千啊
还有IBM的面试官用几个小时来折磨候选人的, 唉, 大公司就是不一样, 不得不佩服你们大公司的人! 是不是大公司的人都这么不把别人的时间当时间啊
@mengzhuo @lijsf @loryyang @geew @bolasblack @cloudzhou @tioover @kamil