遗憾

Question

一个大公司问了什么情况下用二分搜索树，我一下子就晕了我回答的是查找的时候和添加东西的时候，感觉回答的很不理想哎。不知道他要问什么，但是想和他说一下二分法的要有序，哎直接面试失败

Answer 1

liuyubobobo 2021-11-03 06:54:00

树这种数据结构出现的原因，就在于顺序存储数据（数组，链表，等）会使得很多操作的复杂度是 O(n) 级别的。而树让增添改查的操作都降到了 O(logn) 级别。通过这个课程排序部分的介绍，你应该已经看到了，O(n) 和 O(logn) 是差别巨大的。（对应到排序算法中，O(n^2) 的排序算法和 O(nlogn) 的排序算法，是差别巨大的。）

当然了，单纯的二分搜索树是有局限性的，核心局限性是，二分搜索树是可能退化的。因此有了 AVL 树，有了红黑树，他们本质都是二分搜索树，在这个基础上，加入了自平衡的机制。（在我的算法体系课程中，我带领大家实现了基础的 AVL 树和红黑树，只需要在二分搜索树的代码的基础上修改就好了。有兴趣可以参考：https://class.imooc.com/sale/datastructure  ）

当然更进一步，考虑到比如磁盘读写访问扇区的限制，就又有了 B 树或者 B+ 树，他们在名称上已经和二分搜索树没有关系了，但其实背后的思想是一致的（或者说是一脉相承的）。

当然，二分搜索树并不是唯一一个可以快速做增删改查的数据结构，（另外一个经典的数据结构是哈希表），但二分搜索树的另一个主要特性是：有序。既可以快速访问其中每一个元素的前一个元素，后一个元素，快速查找比某一个值大的最小元素，或者比每一个值小的最大元素，以及访问整个数据集中的最大值和最小值。

==========

一两次面试失败是很正常的。整理心情，继续加油！：）

• 提问者 gotodream #1

  bobo老师 ，我又接到一个大公司的面试 给的题目是 给定一个数组 数组无序的且没有重复问 找到那个第k大的元素 当时我的回答是 可以用归并排序因为时间复杂度是o(nlogn) 然后就可以了 然后 他说有没有优化的方法呢我想了一分钟说好像没有了 ，然后我问面试官 说 那你说一下用什么方法优化，他说用二分搜索 我看了网上很多解答都是用快排或者堆排序什么的 没有 说用 二分搜索的 开始因为他说的二分搜索树 后面我想了一下 先要建立一个二分搜索 然后 你要查第k大的 就从最小 或者最大 的开始删除 直到最后删除到那个k元素 最后复杂度应该也又nlogn 最坏的情况下 ，我感觉没有优化， 然后我想了一下是不是我记错了他说的。我越想越觉得离谱 二分搜索的话如果数组如果无序的话，是没有用的但是为什么他说的是二分搜索呢? 后面我又查了一下资料 网上 有个人是这么说的
  按如下步骤在n个元素里面第K大的元素：
  
  第一步：进行一次快排（将大的元素放在前半段，小的元素放在后半段）,得到的中轴p
  第二步：判断 p - low + 1 == k ，如果成立，直接返回a[p]，（前半段有p - low（等于k-1）个大于a[p]元素，则a[p]为第K大的元素）
  第三步：如果 p - low + 1 > k，则第k大的元 素在前半段，更新high = p - 1，执行第一步
  第四步：如果 p - low + 1 < k，则第k大的元素在后半段，更新low = p + 1, 且 k = k - (p - low + 1)，执行第一步
  
  常规快排得到整体有序的数组复杂度是O(nlgn)，此方法每次可以去掉“一半”的元素，复杂度为O(n)
  但是这个我感觉不是二分搜索吧
  链接在这里 bobo老师你帮我看一下
  https://blog.csdn.net/qq_43109561/article/details/90414564
  还有就是 他问了我数组和链表的区别然后 说你可以实现出一个数据结构可以把这两个的优点结合起来吗 我马上想到了一个 hashmap 底层实现 我说了数组加一个红黑树 实现和hashmap 一样就可以 然后他说好 那你有什么要问吗 突然间让我感觉不踏实不知道对错

• liuyubobobo 回复 提问者 gotodream #2

  这个不是二分搜索。你找的资料是正确的，O(n) 的时间找到第 k 大元素使用快排的思想。这个思想在这个课程中提及过，可以参考这里 9 分钟：https://coding.imooc.com/lesson/71.html#mid=1462 我在这个课程中还给出了这个问题的补充代码，可以参考这里：https://git.imooc.com/coding-71/coding-71/src/master/03-Sorting-Advance/Course%20Code%20%28C++%29/Optional-05-Selection/main.cpp
  
  第二个问题回答的很好。继续加油！：）

• 提问者 gotodream 回复 liuyubobobo #3

  但是我今天问了一下是否通过结果说没过真难受我都开始怀疑自己了

点开查看后面1条评论