数组中的二进制搜索 [英] Binary Search in Array
问题描述
我将如何实现只用一个数组的二进制搜索?
How would I implement a binary search using just an array?
推荐答案
请确保您的数组排序,因为这是一个二进制搜索的症结所在。
Ensure that your array is sorted since this is the crux of a binary search.
任何索引/随机存取的数据结构可以是二进制搜索。所以,当你说用只是一个数组,我会说阵列是一个二进制搜索采用的最基本/常见的数据结构。
Any indexed/random-access data structure can be binary searched. So when you say using "just an array", I would say arrays are the most basic/common data structure that a binary search is employed on.
您可以做到这一点递归(容易)或反复。时间二进制搜索的复杂度为O(日志N),这是比检查在O(N)的每个元素的线性搜索快得多。以下是维基百科的一些例子:二进制搜索算法:
You can do it recursively (easiest) or iteratively. Time complexity of a binary search is O(log N) which is considerably faster than a linear search of checking each element at O(N). Here are some examples from Wikipedia: Binary Search Algorithm:
递归:
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = low + ((high - low) / 2)
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
迭代:
BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = low + ((high - low) / 2)
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}
这篇关于数组中的二进制搜索的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!