二分查找的两个前提是什么？
我在一次采访中被问到二分搜索的两个前提条件是什么。我告诉他们数组应该按升序排序，但我不知道二分搜索的第二个前提条件是什么？
谁能告诉我二分搜索的第二个前提？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
数据
Array应该是排序的，并且按照右顺序排序。即：如果当二分搜索采用降序时它按升序排序 - 它不起作用。一些澄清，因为人们似乎忘记了他们的算法 101。
先决条件是一个条件，如果不满足 - 算法不需要提供正确的结果。
随机访问不是二分搜索算法的先决条件，因为即使随机访问不可用，它也可以并且应该返回正确的答案（二分搜索树依赖于此）。
当然不必定义小于运算符，因为它是特定于语言的实现细节。但这很接近事实。
对于任何其他搜索，数据结构必须排序（弱排序）比线性工作。
数据结构的排序顺序必须与二分搜索算法所假定的顺序相同。正如我所提到的，如果数据按升序排序，就像OP所说的那样，并不意味着二分搜索将提供正确的结果，例如，如果搜索是按降序构建的。有多种顺序，升序、降序、字典顺序等。
当您使用二分搜索功能时，您必须确保输入已排序，并且按照您要使用的顺序排序。如果不满足这两个条件 - 您不需要提供正确的结果。
Data
Arrayshould be sorted, and sorted in the right order. 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.
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 must be sorted (weak-ordered) for any search other than linear to work.
Data structure must be sorted in the same order 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.
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.
对二分搜索的前提条件有一个很好的总结此处：
作者只指定了一个前提条件，但我希望您可以将其分解为 2 个彼此相关的条件...
There is a good run-down of the pre-conditions of binary search here:
The author only specifies one pre-condition but I expect you could break it down to 2 conditions that are related to each other...
也许您需要随机访问才能使二分搜索有效。或者至少该数组应该可以多次迭代。
Maybe that you need random access for the binary search to be efficient. Or at least the array should be iterable multiple times.
这些元素必须定义小于运算符。
The elements must have the less-than operator defined.
元素需要位于已排序的数组中，所以我猜它们的意思是
：1）元素位于数组中（或位于任何支持索引访问的数据结构中）。
2）存储按照compare函数排序。
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).
2) The storage is sorted according to the compare function.
这意味着
数组必须排序
使用的排序算法
That means
Arrray must be sorted
Sorting algorithm used