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

Question

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

如果二分搜索仅在数组已排序的情况下使用，那么为什么要如此频繁地比较这两种算法，因为显然它们有不同的用例。

Answer 1

考虑到首先需要 O( n log n ) 工作来对数组进行排序，我是否会在未排序的数组中使用它。

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

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

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