[科普中國(guó)]-二分法搜索

算法簡(jiǎn)介

給予一個(gè)包含n個(gè)帶值元素的數(shù)組A或是記錄A0...An?1，使得A0≤ ... ≤An?1，以及目標(biāo)值T，還有下列用來(lái)搜索T在A中位置的子程序。

令L為0，R為n? 1。

如果L>R，則搜索以失敗告終。

令m（中間值元素）為(L+R) / 2。

如果AmT，令R為m- 1并回到步驟二。

當(dāng)Am=T，搜索結(jié)束；回傳值m。

這個(gè)迭代步驟會(huì)持續(xù)通過(guò)兩個(gè)變量追蹤搜索的邊界。有些實(shí)際應(yīng)用會(huì)在算法的最后放入相等比較，讓比較循環(huán)更快，但平均而言會(huì)多一層迭代1。

復(fù)雜度分析時(shí)間復(fù)雜度

折半搜索每次把搜索區(qū)域減少一半，時(shí)間復(fù)雜度為。（n代表集合中元素的個(gè)數(shù)）

空間復(fù)雜度

。雖以遞歸形式定義，但是尾遞歸，可改寫為循環(huán)。

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