二分法查找算法

时间:2021-12-03 22:09:58

二分法查找的优缺点:
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

非递归二分法查找:

#include <iostream>
using namespace std;
int str[]={1,2,3,4,5,6,7,8,9};
void find_fun(int nu)
{
int len=sizeof(str)/sizeof(int);
int right=len;
int left=0;
do
{
int mid=(right+left)/2;
while(nu<str[mid])
{
right=mid-1;
mid=(right+left)/2;
}

while(nu>str[mid])
{
left=mid+1;
mid=(right+left)/2;
}
if(nu==str[mid])
{
cout<<mid<<endl;
break;
}
}while(str[left]>=nu || nu>=str[right]);


}
int main()
{
find_fun(7);
}

递归二分法查找:

#include <iostream>
using namespace std;
int str[]={1,2,3,4,5,6,7,8,9};
void find_fun(int left,int right,int nu)
{
if(left<=right)
{
int mid=(left+right)/2;
if(str[mid]>nu)
{
right=mid-1;
mid=(left+right)/2;
find_fun(left,right,nu);
}
else if(str[mid]<nu)
{
left=mid+1;
mid=(left+right)/2;
find_fun(left,right,nu);
}
else
{
cout<<mid<<endl;
}
}
else
{
cout<<"left>right"<<endl;
}
}
int main()
{
int right=sizeof(str)/sizeof(int);
find_fun(0,9,1);
}