二分搜索技术

非递归算法;

#include<iostream>
using namespace std;
int BinarySearch(int a[],int x,int n)
{int right=0,left=n-1;while(right<=left){int mid=(right+left)/2;if(x<a[mid])left=mid-1;else if(x>a[mid])right=mid+1;elsereturn mid;}return -1;
}
int main()
{int a[]={0,1,2,3,4,5,6,7,8,9};int x;cin>>x;cout<<BinarySearch(a,x,10);return 0;
}

递归算法;

#include<iostream>
using namespace std;
int BinarySearch(int a[],int x,int right,int left)
{if(right<=left){int mid=(right+left)/2;if(x<a[mid])return BinarySearch(a,x,right,mid-1);else if(x>a[mid])return BinarySearch(a,x,mid+1,left);elsereturn mid;}return -1;
}
int main()
{int a[]={0,1,2,3,4,5,6,7,8,9};int x;cin>>x;cout<<BinarySearch(a,x,0,9);return 0;
}