折半查找的c++模板递归和迭代实现

本文属借鉴他人之作，稍作修改：

折半查找法也称为二分查找法，采用分治策略，可以以O(log n)完成搜索任务，条件就是数组有序。

算法思想：

将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

平时我们看到的都是迭代实现，很少有人去递归，这里给出一个递归的实现。

递归实现：

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

再给一个迭代的，也就是我们平时很经常用到的。

迭代实现：

1. template<classKey>
2. intbinary_search(const Key*r,constint&size,constKey&k)
3. {
4. intlow=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. returnlow;
19. else
20. return-1;
21. }
22. }