维生素b12缺乏诊断:二分搜索算法(折半查找)原理以及递归（recuition），迭代（iteration）的两种实现源代码

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

【基本思想】

将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。

二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。

C++描述

1. template    
2. int BinarySearch(Type a[],const Type& x,int n)     
3. {     
4. int left=0;    
5. int right=n-1;    
6. while(left<=right){     
7. int middle=(left+right)/2;    
8. if (x==a[middle]) return middle;    
9. if (x>a[middle]) left=middle+1;    
10. else right=middle-1;    
11. }     
12. return -1;    
13. }  

templateint BinarySearch(Type a[],const 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>a[middle]) left=middle+1;else right=middle-1;}return -1;}

递归实现（recuition）

1. template    
2. int binary_search( Record * r, const int & low, const int & high, const Key & k )    
3. {    
4. int mid = (low + high)/2;    
5. if( low < high )    
6. {    
7.   if( k <= r[mid] )    
8.    binary_search( r, low, mid, k );     
9.   else    
10.    binary_search( r, mid+1, high, k );    
11. }    
12. else if( low == high )    
13. {    
14.   if( k == r[mid] )    
15.    return low;    
16.   else    
17.    return -1;    
18. }    
19. else    
20.   return -1;    
21. }  

templateint binary_search( Record * r, const int & low, const int & high, const Key & k ){int mid = (low + high)/2;if( low < high ){if( k <= r[mid] )binary_search( r, low, mid, k );elsebinary_search( r, mid+1, high, k );}else if( low == high ){if( k == r[mid] )return low;elsereturn -1;}elsereturn -1;}

 迭代实现（iteration）

1. template    
2. int binary_search( Record * r, const int & size, const Key & k )    
3. {    
4. int low=0, high=size-1, mid;    
5. while( low < high )    
6. {    
7.   mid = (low + high) / 2;    
8.   if( k > r[mid] )    
9.    low = mid + 1;    
10.   else    
11.    high = mid;    
12. }    
13. if( low > high )    
14.   return -1;    
15. else    
16. {    
17.   if( k == r[low] )    
18.    return low;    
19.   else    
20.    return -1;    
21. }    
22. }