简单的问题串联可以组成复杂!
给定已经排好序的n个元素a[0...n-1],现在在这n个元素中找出一特定元素x。
代码如下:
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
template <class Type>
int BinarySearch(Type a[],Type& x,int n)


{
int left=0;
int right=n-1;

while(left<=right)

{
int middle=(left+right)/2;

if(x==a[middle])
return middle;

if(x>middle)
left=middle+1;

else
right=middle-1;
}
return -1;
}

template <class Type> //重载
int BinarySearch(Type a[],Type& x,int left,int right)


{
int middle=(left+right)/2;

if(x==a[middle])
return middle;

else if(x>middle)
return BinarySearch(a,x,middle+1,right);

else
return BinarySearch(a,x,left,middle-1);

return -1;
}

int main()


{
int i,n,x;
int a[100];
while(scanf("%d",&n)!=EOF)

{
for(i=0;i<n;i++)
scanf("%d",&a[i]);

sort(a,a+n);

for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");

scanf("%d",&x);

printf("%d\n",BinarySearch(a,x,n));

printf("%d\n",BinarySearch(a,x,0,n-1));
}
return 0;
}
运行结果:
posted on 2010-09-07 22:42
jince 阅读(207)
评论(0) 编辑 收藏 引用 所属分类:
算法设计与分析