algorithm - 为什么在未排序的数组中我更喜欢二进制搜索而不是线性搜索？

Question

我一直在 Coursera 上学习 DSA 类(class)，本周学习了搜索算法。而二分查找的复杂度(O(logn))优于线性查找(O(n))。但是，考虑到需要 nlogn 工作才能首先对数组进行排序这一事实，我为什么要在未排序的数组中使用它。

如果二分查找只用于数组已经排序的地方，那么为什么要经常比较这两种算法，因为很明显它们有不同的用例。

Answer 1

would I ever use it in an unsorted array given the fact that it would take O(n log n) work to sort the array first.

通常一个人对同一个数据结构执行多个查询。确实，例如查看数据库。与添加记录相比，使用给定主键获取记录的频率更高是有道理的。这是有道理的，因为如果查询的数量低于插入的数量，那么我们插入的数据永远不会被检索到，因此这些是“无用的”。

此外，对元素列表进行排序，或构建元素的二叉树确实需要 O(n log n)。但是更新二叉搜索树，例如 AVL tree [wiki]需要 O(log n)。因此，如果您通过添加一个元素、删除一个元素、更新一个元素等方式稍微更改元素集合。它需要 O(log n) 来更改数据结构，并且您会继续维护O(log n) 查找。

对未排序的数据使用线性搜索，对于少量查询确实会优于排序和二分搜索。从查询数量变大的那一刻起，线性搜索算法就会被二分搜索算法超越。