c - 二分查找的两个先决条件是什么？

Question

<分区>

Answer 1

数据 Array 应该被排序，并且以正确的顺序排序。即:如果在二进制搜索采用降序时按升序排序 - 它不会起作用。

一些澄清，因为人们似乎忘记了他们的算法 101。

Precondition 是一个条件，如果不满足 - 算法不需要提供正确的结果。

随机访问不是二分搜索算法的先决条件，因为它可以而且应该返回正确的答案，即使随机访问不可用(二分搜索树依赖于此)。

当然不必定义小于运算符，因为它是特定于语言的实现细节。但这很接近事实。

数据结构必须排序 ( weak-ordered ) 才能使线性搜索以外的任何搜索都起作用。

数据结构必须按与二进制搜索算法假定的顺序相同的顺序排序。正如我所提到的，如果数据按升序排序，就像 OP 所说的那样，这并不意味着二进制搜索将提供正确的结果，例如，如果搜索是按降序构建的。顺序有很多，升序、降序、字典序等等。

当您使用二进制搜索功能时，您必须确保输入已排序，并按照您要使用的顺序排序。如果不满足这两个条件 - 您不需要提供正确的结果。