算法：BINARYSEARCHREC
偽代碼如下：
輸入：按非降序排列的n個(gè)元素的數(shù)組A[1...n]和元素x
輸出：如果x=A[j]，則輸出j，否則輸出0
binarysearch(1,n)
binarysearch(low,high)
if low>high then return 0
else
? ? mid?←(low+high)/2
? ? if x=A[mid] then return mid
? ? else if x<a[mid] then return?binarysearch(low,mid-1)
? ? else return?binarysearch(mid+1，high)
end if
時(shí)間復(fù)雜度為：Ο（logn）
詳細(xì)代碼如下：
int binary_search_recursion(const int array[], int low, int high, int key)
{
? ? int mid = low + (high - low)/2;
? ? if(low > high)
? ? ? ? return -1;
? ? else{
? ? ? ? if(array[mid] == key)
? ? ? ? ? ? return mid;
? ? ? ? else if(array[mid] > key)
? ? ? ? ? ? return binary_search_recursion(array, low, mid-1, key);
? ? ? ? else
? ? ? ? ? ? return binary_search_recursion(array, mid+1, high, key);
? ? }
}
