今天同事在讨论下午来面试的那个人，然后说下次面试应该多加个算法题，二分递归排序，还特别强调了递归，然后我说二分不是本来就是递归的么。。。然后他说你被秒了。。
额，我太水了。。丢人的。。。
方法1：递归
#include <iostream.h>
#define SIZE 10
int data[SIZE] = {10,20,30,40,50,60,70,80,90,100};
int two_search(int start, int end, int val);
main()
{
int val;
int p;
cin>>val;
p=two_search(0, SIZE-1, val);
if (p != -1)
cout<<"Search"<<data[p]<<"is"<<p+1 <<" count!";
else
cout<<"no found!";
return 0;
}
int two_search(int start, int end, int val)
{
int p = (start+end)/2;
if(data[p]!=val)
{ if (start>end)
return -1;
if (data[p] > val)
two_search(start,p-1,val);
else
two_search(p+1,end,val);
}
else return p;
}
方法2：递归
#include<iostream>
#define S 10
using namespace std;
int binarysearch(int a[],int left,int right,int numtofind)
{
if(a[(left+right)/2]!=numtofind)
{
if(left > right) return -1;
if(a[(left+right)/2]>numtofind) binarysearch(a,left,(right+left)/2-1,numtofind);
else binarysearch(a,(left+right)/2+1,right,numtofind);
}
else return (left+right)/2;
}
int main()
{
int a[S]={0,1,3,5,6,9,10,12,16,19};
int n;
int pos;
cin>>n;
pos=binarysearch(a,0,S-1,n);
cout<<"the num is on pos:"<<pos<<endl;
}
方法3：循环
#include<iostream>
using namespace std;
int binary_search(int a[],int beg,int end,int num)
{
if (beg>end) return -1;
if (num==a[(beg+end)/2]) return (beg+end)/2;
else return num>a[(beg+end)/2]?binary_search(a,(beg+end)/2+1,end,num):binary_search(a,beg,(beg+end)/2-1,num);
}
int main()
{
int a[10]={1,2,3,4,5,7,8,9,10,11};
cout<<binary_search(a,0,9,6);
}
方法四：循环
#include<iostream>
#include<algorithm>
using namespace std;
int binarysearch(int a[],int left,int right,const int &value)
{
while(left<=right)
{
int middle=(left+right)/2;
if(a[middle]==value) return middle;
else if(value>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
int main()
{
int a[10]={3,2,1,4,5,6,8,9,7,0};
sort(a,a+10);
int n;
cin>>n;
if(binarysearch(a,0,9,n)==-1)
cout<<"no"<<endl;
else
cout<<"yes"<<endl;
}
转载于:https://my.oschina.net/u/211101/blog/39802