在王道论坛上看到13级中科大CS复试的面试题，有道友说到面试官问了这样的问题：
1.二分查找（单链表)复杂度
2.写出二分查找用链表实现的时间复杂度递推公式
3.二叉查找的时间复杂度
4.二分法用链表和顺序表哪个更好，为什么？查中间那个节点时间复杂度是多少？
先不说以上问题的答案如何，如果是我遇到的话，我想我只能回答第3个问题。原因如下：
1.二分查找又称折半查找，而折半查找能使用的情况必须同时满足两个条件：a.待排记录序列必须按关键字有序    b.必须采用顺序存储结构
因此二分查找根本不能用链式存储结构，换句话说，二分查找不能用线性链表来实现，而只能用顺序表来实现。另外我们通常称描述二分查找过程的二叉树为二叉判定树(注意与下文的二叉查找树区别)。至于二分查找的时间复杂度，我想大家都知道，就不说了。
2.二叉查找是从二叉查找树(又称二叉排序树)而来,通常二叉查找树采用的是二叉链表的存储结构。二叉查找的时间复杂度(也就是上面的第3个问题)，不能笼统地说是O(logN),因为二叉查找树的平均查找长度与树的形态有关。分三种情况：a.最坏的情况，即先后插入的关键字有序时，构成的二叉查找树蜕变为单枝树（除了最后一个叶结点之外，每个结点有且只有一个子结点），其平均查找长度为(n+1)/2,此时的时间复杂度就是O(N)。
b.最好的情况，即二叉查找树的形态和二分查找的二叉判定树相同，其平均查找长度和logN成正比，此时的时间复杂度当然是O(logN)。
c.在随机的情况下，二叉查找树的平均查找长度和是logN等数量级的,此时的时间复杂度可视为O(logN)。
3.二分查找和二叉查找的关系是：二叉查找既拥有类似于二分查找的特性，又采用了链表作为存储结构。
综上，以上题目本身及题目答案已不是重点，希望面试官提的问题严谨些。

你想表达什么？  

二分查找是可以用链表实现的，就是非常蛋疼。可能是面试官的问题很蛋疼，或者说那个同学把二分查找和二叉查找打错了

好信息的总结啊~~~顶一个

看着你的题目又想起复试那天