[科普中国]-二分搜索法

简介

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。1

如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。

算法步骤给予一个包含n个带值元素的数组A或是记录A0...An−1，使得A0≤ ... ≤An−1，以及目标值T，还有下列用来搜索T在A中位置的子程序。

令L为0，R为n− 1。

如果L>R，则搜索以失败告终。

令m（中间值元素）为“(L+R) / 2”加上下高斯符号。

如果AmT，令R为m- 1并回到步骤二。

当Am=T，搜索结束；回传值m。

这个迭代步骤会持续通过两个变量追踪搜索的边界。有些实际应用会在算法的最后放入相等比较，让比较循环更快，但平均而言会多一层迭代。2

大致匹配以上程序只适用于完全匹配，也就是查找一个目标值的位置。不过，因为有序数组的顺序性，将二分搜索算法扩展到能适用大致匹配并不是很重要。举例来说，二分搜索算法可以用来计算一个赋值的排名（或称秩，比它更小的元素的数量）、前趋（下一个最小元素）、后继（下一个最大元素）以及最近邻。搜索两个值之间的元素数目的范围查询可以借由两个排名查询（又称秩查询）来运行。

排名查询可以使用调整版的二分搜索来运行。借由在成功的搜索回传m，以及在失败的搜索回传L，就会取而代之地回传了比起目标值小的元素数目。

前趋和后继查询可以借由排名查询来运行。一旦知道目标值的排名，其前趋就会是那个位于其排名位置的元素（因为它是小于目标值的最大元素）。其后继是（数组中的）下一个元素，或是（非数组中的）前趋的下一个元素。目标值的最近邻可能是前趋或后继，取决于何者较为接近。

范围查询也是直接了当的。一旦知道两个值的排名，不小于第一个值且小于第二个值的元素数量就会是两者排名的差。这个值可以根据范围的端点是否算在范围内，或是数组是否包含其端点的对应键来增加或减少1。

代码我们可用C++描述如下：

template

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(lefta[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

或者：

/*找到目标值时返回值为下标，找不到时返回如果要加入此数，应该放置的下标（负数表示）*/

int binarySearch (int arrays[], int size, int num)

{

int low = 0, high = size - 1;

while ( high > low )

{

int mid = (low + high) / 2;

if ( num > arrays[mid] )

low = mid + 1;

else if (num

high = mid - 1;

else if (num == arrays[mid])

return mid;

}

return -low - 1;

}

第一个模板函数BinarySearch在a[0]