Data Structures Algorithms 简明教程
Binary Search Algorithm
二分查找是一种具有 O(log n) 运行时复杂度的快速搜索算法。此搜索算法基于分而治之的原理，因为它在搜索之前将数组分成两半。为了使此算法正常工作，数据收集应采用已排序的形式。
二分查找通过比较集合中最中间的项来查找特定的键值。如果发生匹配，则返回项的索引。但是，如果中间项的值大于键值，则搜索中间项的右子数组。否则，搜索左子数组。此过程会递归地继续，直到子数组的大小减小为零。
Binary Search Algorithm
二分查找算法是一种仅在间隔内执行查找的间隔查找方法。二分查找算法接受的输入必须始终是一个经过排序的数组，因为它根据较大的值或较小的值将数组划分为子数组。该算法遵循以下过程：
Step 1 − 选择数组中的中间项并将其与要搜索的键值进行比较。如果匹配，则返回中值的索引。
Step 2 − 如果它不匹配键值，请检查键值是否大于或小于中值。
Step 3 − 如果键更大，则在右子数组中执行搜索；但如果键低于中值，则在左子数组中执行搜索。
Step 4 − 重复步骤 1、2 和 3，直到子数组的大小变为 1。
Step 5 − 如果键值在数组中不存在，则算法将返回不成功的搜索。
Pseudocode
二分搜索算法的伪代码看起来是这样的：
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedureAnalysis
由于二进制搜索算法以迭代方式执行搜索，因此计算时间复杂度并不像线性搜索算法那样容易。
每次不成功的迭代之后，通过划分为多个子数组来迭代搜索输入数组。因此，形成的递归关系将是一个除法函数。
用更简单的术语解释，
-
在第一次迭代中，在整个数组中搜索元素。因此，数组长度 = n。
-
在第二次迭代中，只搜索原始数组的一半。因此，数组长度 = n/2。
-
在第三次迭代中，搜索前一个子数组的一半。在此，数组的长度 = n/4。
-
同样，在第 i 次迭代中，数组的长度将变成 n/2i
为了实现成功的搜索，在最后一次迭代之后，数组的长度必须为 1。因此，
n/2i = 1这给我们 −
n = 2i对两侧应用 log，
log n = log 2i
log n = i. log 2
i = log n二分搜索算法的时间复杂度为 O(log n)
Example
为了进行二分查找，目标数组必须已排序。我们通过一个图片示例学习二分查找的过程。以下是我们已排序的数组，让我们假设我们需要使用二分查找搜索值 31 的位置。
首先，我们将使用以下公式确定数组的一半 −
mid = low + (high - low) / 2即为 0 + (9 - 0) / 2 = 4（4.5 的整数部分）。因此，4 是该数组的中间位置。
现在我们比较存储在位置 4 处的该值与要搜索的值（即 31）。我们发现位置 4 处的该值为 27，不匹配。由于该值大于 27 且我们有一个已排序的数组，因此我们还知道目标值肯定位于数组的上半部分。
我们将 low 更改为 mid + 1，并再次找到新的 mid 值。
low = mid + 1
mid = low + (high - low) / 2我们的新 mid 值现在为 7。将存储在位置 7 处的该值与我们的目标值 31 进行比较。
存储在位置 7 的值不是匹配项，而是我们正在寻找的值那个更小。因此，该值必须在这个位置的较低部分。
因此，我们再次计算中间值。这次是 5。
我们将存储在位置 5 的值与我们的目标值进行比较。我们发现这是一个匹配项。
我们得出结论，目标值 31 存储在位置 5。
二分查找将可搜索项减半，从而将要进行的比较次数减少到极小数量。