二分查找 binarySearch 适合初学分析的例子

递归代码：

#include <cstdio>
#include <algorithm>
#define MAX 5
using namespace std;
 
int binarySearch(int x,int a[],int left,int right);
 
int main()
{
    int a[MAX]={1,3,4,5,9};
    printf("find %d location is %d\n",4,binarySearch(4,a,0,MAX-1));
    printf("find %d location is %d\n",11,binarySearch(11,a,0,MAX-1));
    printf("find %d location is %d\n",9,binarySearch(9,a,0,MAX-1));
    return 0;
}
 
int binarySearch(int x,int a[],int left,int right)
{
    int mid=left+(right-left)/2;
    if(left<=right)
    {
        if(a[mid]==x)return mid;
        else if(a[mid]>x)return binarySearch(x,a,left,mid-1);
        else return binarySearch(x,a,mid+1,right);
    }
    return -1;//fail
}

分析：

注意第20行判断语句为 left<=right 

运行结果：

 非递归代码：

#include <cstdio>
#include <algorithm>
#define MAX 5
using namespace std;
 
int binarySearch(int x,int a[],int left,int right);
 
int main()
{
    int a[MAX]={1,3,4,5,9};
    printf("find %d location is %d\n",4,binarySearch(4,a,0,MAX-1));
    printf("find %d location is %d\n",11,binarySearch(11,a,0,MAX-1));
    printf("find %d location is %d\n",9,binarySearch(9,a,0,MAX-1));
    return 0;
}
 
int binarySearch(int x,int a[],int left,int right)
{
    int mid;
    while(left<=right)
    {
        mid = left+(right-left)/2;
        if(a[mid]==x)return mid;
        else if(a[mid]>x)
            right = mid-1;
        else left = mid+1;//mid值已经比较过了，所以进行加一减一操作去掉这一点
    }
    return -1;//fail
}

 运行结果：