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

算法简介

给予一个包含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。

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

复杂度分析时间复杂度

折半搜索每次把搜索区域减少一半，时间复杂度为。（n代表集合中元素的个数）

空间复杂度

。虽以递归形式定义，但是尾递归，可改写为循环。

代码C++#include#define N 10using namespace std;int main(){ int a[N],front,end,mid,x,i; cout