二进制搜索是一种快速搜索算法,运行时复杂度为O(log n).这种搜索算法的工作原则是分而治之.为使此算法正常工作,数据收集应采用排序形式.
二进制搜索通过比较集合的最中间项来查找特定项.如果匹配发生,则返回项目的索引.如果中间项大于项,则在中间项左侧的子阵列中搜索项.否则,在中间项右侧的子阵列中搜索项.此过程在子数组上继续,直到子数组的大小减小到零.
对于二进制搜索工作,必须对目标数组进行排序.我们将用一个图例来学习二元搜索的过程.以下是我们的排序数组,让我们假设我们需要使用二进制搜索来搜索值31的位置.
首先,我们将使用此公式确定数组的一半 :
mid = low + (高 - 低)/2
这里是,0 + (9 - 0)/2 = 4(整数值为4.5).所以,4是数组的中间.
现在我们将位置4存储的值与搜索的值进行比较,即31.我们发现位置4的值是27,这不匹配.由于值大于27并且我们有一个排序数组,所以我们也知道目标值必须位于数组的上半部分.
我们将低音改为中音 + 1并再次找到新的中间值.
low = mid + 1 mid = low + (high - low)/2
我们新的中期现在是7.我们将位置7存储的值与目标值31进行比较.
存储在位置7的值不匹配,而是比我们正在寻找的值更多.因此,该值必须位于此位置的下半部分.
因此,我们再次计算中间值.这次是5.
我们比较值使用我们的目标值存储在位置5.我们发现它是一个匹配.
我们得出结论目标值31存储在位置5.
二进制搜索将可搜索项目减半,从而减少了对比数非常少的比较次数.
二进制搜索算法的伪代码应如下所示;
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 procedure
要了解使用C编程语言中的数组的二进制搜索实现.