用折半法查找

题目是这样的：
一个整形有序数组，假设是{0,1,2,3,4,5,6,7,8,9}
输入一个数字，要求先与中间的数比较，比中间的大，
就只与中间后面的数相比较，否则，与前面的数比较。


哪位大虾帮帮忙，小弟先谢过了~~~

/*---------------------------------------------------------------------------
File name: binary_search.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/5/2007 15:04:19
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

*/

#include <stdio.h>

#define DIM(x) sizeof((x))/sizeof((x)[0])

/** Binary search.

Pre-condition: the array a is sorted, either
ascending (1 2 3 4 5) or descending (5 4 3 2 1).

Post-condition: return the index of the search key.
*/
int binary_search(int* a, unsigned int n, int key)
{
int low = 0, high= n-1, mid;

if(n<1)
{
printf("invalid input for n.\n");
return -1;
}

if(a[0]<=a[n-1]) /// the array is sorted ascending
{
while(low<=high) /// don't forget =
{
mid=(high+low)/2;

if(a[mid]<key)
low=mid+1;
else if(a[mid]>key)
high=mid-1;
else
return mid;
}
}
else /// the array is sorted descending
{
while(low<=high) /// don't forget =
{
mid=(high+low)/2;

if(a[mid]<key)
high=mid-1;
else if(a[mid]>key)
low=mid+1;
else
return mid;
}
}

return -1;
}

int main()
{
int a[]={-4, -2, -1, 0, 2, 7, 9, 11};

int i=binary_search(a, DIM(a), 0);

printf("i = %d\n",i);

return 0;
}

[CODE]#include <iostream>
using namespace std;


int binarySearch_recursive(int a[],int key,int left,int right){
int range = right - left;
int i = left + range/2;
if (range < 2)
return -1;
else if (key == a[i])
return i;
else if (key < a[i])
return binarySearch_recursive(a,key,left,i);
else if (key > a[i])
return binarySearch_recursive(a,key,i,right);
}

int binarySearch_iterative(int a[],int key,int left,int right){
while (right - left > 1){
int range = right - left;
int i = left + range/2;
if (key == a[i])
return i;
else if (key < a[i])
right = i;
else if (key > a[i])
left = i;
}
return -1;
}

int main(){
int a[] = {1,2,3,4,5,6,7,8,9,10};
cout << binarySearch_recursive(a,4,0,9) << endl;
cout << binarySearch_iterative(a,8,0,9) << endl;
system("pause");

}[/CODE]

两个版本都有，*_*

#include <vector>
#include <iostream>
using namespace std;

template<class IT>
int BinarySearch(IT _FI,IT _FL,typename iterator_traits<IT>::value_type key)
{
 int pos=0;
 IT _PI=_FI+(_FL-_FI)/2,_PL=_FL-1;
 if(*_PI==key)return (int)(_FL-_FI)/2;
 if(_FI==_PL)return -1;
 if(*_PI>key)return BinarySearch(_FI,_PI,key);
 else return (pos=BinarySearch(_PI,_FL,key))==-1?-1:(int)(_FL-_FI)/2+pos;
}


void main()
{
 int a[]={1,2,3,4,5,6,7,8,9,10};
 vector<int>aa(a,a+10);
 cout<<BinarySearch(a,a+10,11)<<endl;
 cout<<BinarySearch(aa.begin(),aa.end(),4)<<endl;
}

谢谢
不过似乎看起来还是有些难懂
要考试了
考完试在慢慢琢磨吧
谢谢了
呵呵