二分查找在C++中的实现

在计算机科学中，折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二分查找要求：
1.必须采用顺序存储结构
2.必须按关键字大小有序排列。

二分查找的步骤 ：

二分查找可以解决预排序数组的查找问题。假设表中元素是按升序排列，只要数组中包含T（即要查找的值），

那么通过不断的缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组，
将数组的中间项与T进行比较，可以排除一般的元素，范围缩小一半。就这样反复比较反复缩小范围，
最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，
整个查找过程大约要经过Log（2）N次比较。

注意：二分查找是针对有序的数组而言的。

复杂度分析
时间复杂度折半搜索每次把搜索区域减少一半，时间复杂度为。（n代表集合中元素的个数）空间复杂度 。虽以递归形式定义，但是尾递归，可改写为循环。

折半（二分）查找的c++代码（递归和非递归）实现 - 下载频道 - CSDN.NET http://download.csdn.net/detail/qq_34536551/9840748