分治算法-折半搜索

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int bin_search(int a[],int left,int right,int x)
 5 {
 6     if(left<=right)
 7     {
 8         int mid=(left+right)/2;
 9         if(x<a[mid])
10             return bin_search(a,left,mid-1,x);
11         else if(x>a[mid])
12             return bin_search(a,mid+1,right,x);
13         else
14             return mid;
15     }
16     else
17         return -1;
18 }
19 int main()
20 {
21     int a[10]={1,3,5,7,9,11,13,14,15,16};
22     int x=10;
23     int pos=bin_search(a,0,9,x);
24     if(pos!=-1)
25         cout<<pos<<" "<<a[pos]<<endl;
26     else
27         cout<<x<<"不存在"<<endl;
28     return 0;
29 }