二分查找，有序数组

Question

5

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

这种方法是否需要容器已排序？否则，我不明白如何通过比较容器中的关键字和值来消除容器的部分以查找并且它有什么特殊用途。

- Mars

4

是的，二分查找只适用于已排序的集合。任何没有明确说明这一点的文章都是不充分的 :( - Jon Skeet

4

谁在给这个点踩？问题清晰明了，包含动机，展示了理解，并且与编码密切相关。"我知道这个，怎么可能有人不知道" 不是给问题点踩的充分理由。 - us2012

1

@us2012 这是关于在提问之前没有做足够的研究。几乎所有与二分查找相关的文章都会非常清楚地提到这一点。 - Saksham

@Saksham。我之所以提出这个问题，是因为我正在浏览众多技术面试编程书籍之一，而在我看的那本书中，并没有提到这一点。当然，我相信作者假设读者已经了解这个事实，但这是一个例子，其中并未提及。 - Mars

2个回答

3

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

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

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

- trungdinhtrong

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joni · Accepted Answer

是的，它可以。

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

来源：维基百科：二分查找算法，但任何其他合适的算法文本都应该提到数组必须是已排序的。