用遞歸法寫一個(gè)折半查找的算法？半搜索需要先對(duì)數(shù)據(jù)進(jìn)行排序。以上是氣泡排序算法的實(shí)現(xiàn)。半搜索算法描述如下：在一個(gè)有序表中，將要搜索的數(shù)據(jù)值與搜索范圍的中間元素值進(jìn)行比較，會(huì)出現(xiàn)三種情況：1）如果要搜索的

用遞歸法寫一個(gè)折半查找的算法？

半搜索需要先對(duì)數(shù)據(jù)進(jìn)行排序。以上是氣泡排序算法的實(shí)現(xiàn)。半搜索算法描述如下：在一個(gè)有序表中，將要搜索的數(shù)據(jù)值與搜索范圍的中間元素值進(jìn)行比較，會(huì)出現(xiàn)三種情況：

1）如果要搜索的數(shù)據(jù)值正好等于中間元素值，則放回中間元素值的索引。

2）如果要搜索的數(shù)據(jù)的值小于中間元素的值，則整個(gè)搜索范圍的前半部分將用作新的搜索范圍，并且1）執(zhí)行，直到找到相等的值。

3）如果要搜索的數(shù)據(jù)的值大于中間元素的值，則整個(gè)搜索范圍的后半部分將用作新的搜索范圍，并執(zhí)行1）直到找到相等的值。4） 如果最后找不到相等的值，則返回錯(cuò)誤消息。實(shí)現(xiàn)過(guò)程如下：復(fù)雜性分析：半搜索就像搜索素?cái)?shù)二叉樹：中間值是二叉樹的根，前半部分是左子樹，后半部分是右子樹。半搜索方法的搜索次數(shù)正好是值所在的層數(shù)。在等概率的情況下，它是關(guān)于log2（n1）-1的，算法復(fù)雜度為O（logn）。

折半查找算法及代碼？

#include<iostream>

#使用命名空間std

模板<class T>

int BinarySearch（ta[]，const T&x，int n，int left，int right）

{

if（left>=right）

return-1

else

{

if（a[（left right）/2]==x）

return else if（x>=（left）右）/2）

返回二進(jìn)制搜索（a，x，n，（左-右）/21，右）

else if（x<（左-右）/2）

返回二進(jìn)制搜索（a，x，n，左，（左-右）/2-1）

}

}

int main（）

{

int a[MAXSize

]int i，len，x，P

CIN>>len

for（I=0I<leni）

CIN>>A[I

]CIN>>X

P=binarysearch（a，x，len，0，len-1）

if（P==-1）

cout<<“數(shù)字不存在！”！“<<endl

else

cout<<p 1<<endl

返回0

}