二分法查找（递归实现，非递归实现）

递归实现：

#include <iostream>

using namespace std;

//递归实现二分查找
int Find(int A[],int a,int b,int key)
{
    if(a>b)
        return 0;
    int mid = (a+b)/2;
    if(A[mid]==key)
        return mid;
    else if(key<A[mid])
        return Find(A,a,mid-1,key);
    else
        return Find(A,mid+1,b,key);
}
int main()
{
    //直接构造一个有序数组
    int A[11];
    for(int i=1;i<11;i++)
    {
        A[i]=i;
    }
    int pivort=Find(A,1,10,8);//查找值为8的数组下标
    if(pivort==0)
        cout<<"Not Find"<<endl;
    else
        cout<<pivort<<endl;
    return 0;
}

非递归实现：

#include <iostream>

using namespace std;

//非递归二分查找
int Find(int A[],int a,int b,int key)
{
    int mid;
    while(a<b)
    {
        mid=(a+b)/2;
        if(key==A[mid])
            return key;
        else if(key<A[mid])
            b=mid-1;
        else
            a=mid+1;
    }
    return 0;
}

int main()
{
    int A[11];
    for(int i=1;i<11;i++)
    {
        A[i]=i;
    }
    int pivort=Find(A,1,10,8);
    if(pivort==0)
        printf("Not Find\n");
    else
        cout<<pivort<<endl;
    return 0;
}

感悟：之前对二分法的理解总停留在递归层面上，通过实现了非递归发现无论是递归还是循环，只要想办法把算法的过程实现就好了，思路都是一样的。