二分法查找算法

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

非递归二分法查找：

#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);
}