C语言 二分查找的两个先决条件是什么？

What are the two precondition on Binary search?

提问by Amit Singh Tomar

i have been asked in an interview what are the two preconditions of the binary search .I have told them array should be sorted in ascending order but i didn't know what could be the second precondition of binary search?

我在一次采访中被问到二分搜索的两个先决条件是什么。我告诉他们数组应该按升序排序，但我不知道二分搜索的第二个先决条件是什么？

Anyone can tell me about the second precondition of Binary search?

谁能告诉我二分搜索的第二个先决条件？

回答by littleadv

Data Arrayshould be sorted, and sorted in the rightorder. I.e.: if its sorted in ascending order when the binary search assumes descending order - it won't work.

数据数组应该排序，并按正确的顺序排序。即：如果它在二进制搜索采用降序时按升序排序 - 它将不起作用。

Some clarifications, as it seems that people forgot their Algorithms 101.

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

Precondition is a condition, that if not met - the algorithm is not required to provide the correct result.

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

Random access is not a precondition for a binary search algorithm, as it can and should return the correct answer even if the random access is not available (Binary Search Trees rely on that).

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

less-than operator certainly doesn't have to be defined, as it is a language-specific implementation detail. But it is close to the truth.

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

Data structure mustbe sorted (weak-ordered) for any search other than linear to work.

必须对数据结构进行排序（弱排序）才能使线性以外的任何搜索工作。

Data structure must be sorted in the sameorder as the one assumed by the binary search algorithm. As I mentioned, if the data is sorted in the ascending order, like the OP said, it doesn't mean that the binary search will provide the correct result, if the search is built for descending order, for example. There are many orders, ascending, descending, lexicographic, etc etc.

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

When you use a binary search function you must ensure that the input is sorted, and sorted to the order you're going to use. If these two are not met - you're not required to provide correct result.

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

回答by seanhodges

There is a good run-down of the pre-conditions of binary search here:

目前的二进制搜索的先决条件良好的破败这里：

The array must be sorted in ascending order according to the ordering used by the comparisons in the search function.

数组必须根据搜索函数中比较所使用的顺序按升序排序。

The author only specifies one pre-condition but I expect you could break it down to 2 conditions that are related to each other...

作者只指定了一个前提条件，但我希望您可以将其分解为两个相互关联的条件...

• Must be sorted in ascending or descending order, depending on your search algorithm
• Input must be compatible with the comparisonalgorithm

• 必须按升序或降序排序，具体取决于您的搜索算法
• 输入必须与比较算法兼容

回答by Juraj Blaho

Maybe that you need random access for the binary search to be efficient. Or at least the array should be iterable multiple times.

也许您需要随机访问才能使二进制搜索有效。或者至少数组应该可以迭代多次。

回答by Secure

Elements need to be in a sorted array, so I guess they mean

元素需要在一个排序的数组中，所以我猜他们的意思是

1) The elements are in an array (or in any data structure that enables indexed access).

1) 元素在数组中（或在任何支持索引访问的数据结构中）。

2) The storage is sorted according to the compare function.

2) 根据比较函数对存储进行排序。

回答by lsunny

That means

这意味着

1. Arrray must be sorted

2. Sorting algorithm used

1. 数组必须排序

2. 使用的排序算法

回答by orlp

The elements must have the less-than operator defined.

元素必须定义小于运算符。