簡單的問題串聯(lián)可以組成復(fù)雜！
給定已經(jīng)排好序的n個元素a[0...n-1]，現(xiàn)在在這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;
}運行結(jié)果：
posted on 2010-09-07 22:42
jince 閱讀(222)
評論(0) 編輯 收藏 引用 所屬分類:
算法設(shè)計與分析