c++ - 二分查找，排序数组

Question

我正在学习二进制搜索，基本定义从第一个元素的迭代器和最后一个元素的迭代器开始。您还有一个键，这是您要查找的元素。首先将key与中点的值进行比较，然后根据key是大于还是小于中点的值来消除上半部分或下半部分。并且该过程一直持续到匹配为止。

这种方法不需要对您正在查看的容器进行排序吗？否则，我看不出容器中的键和值之间的比较以消除要查看的容器部分有何特殊用途。

Answer 1

是的，它确实。

在计算机科学中，二分搜索或半间隔搜索算法在按键值排序的数组中查找指定输入值（搜索“键”）的位置。

资料来源：维基百科：二进制搜索算法，尽管算法上的任何其他体面的文本都应该提到必须对数组进行排序。

Answer 2

答案是肯定的。二进制搜索假设您首先对集合进行排序。如果我没记错的话，任何性能优于 O(N) 的搜索算法都要求您的集合存储在一些特殊的数据结构中（排序列表、二叉树、红黑树......）。

当你实现一个集合的二分搜索时，你必须确保这个集合首先被排序。通常你会先对列表进行排序，然后总是在正确的位置添加元素（以确保新集合仍然是排序的）。假设您还使用二进制搜索来找到要添加的正确位置，在最坏的情况下，添加和搜索都是 O(log2(N))。

当您考虑不同的搜索算法时，您还必须考虑底层数据结构和向其中添加元素的成本。