折半(二分)查找
《递归入门》
百度百科：折半(二分)查找
假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
折半(二分)查找也是一个分而治之策略的完美示例。所以，其可以用递归实现也不足为奇。
解法：递归
递归的作用在于把问题的规模不断缩少，直到问题缩少到能简单地解决
由于我们查找的须是一个有序表，所以在每一次的比较中，缩少的规模将是上一次查找规模的一半，可见这效率是相当大
新问题与原问题有着相同的形式
新问题与原问题具有相同的形式，就是查找某个字符
递归的结束需要简单情景
递归跳跃的信任
由于实现细节较易就能看出，未能突出体现出递归跳跃的信任的重要性
#include <iostream>using namespace std;int bin_search(int *p, int low, int high, int key){int mid;mid = (low + high) / 2;if (p[mid] == key) return 1;//返回 1 代表查找成功，反之失败if (low > high) return 0;if (key > p[mid]){return bin_search(p, mid+1, high, key);}else{return bin_search(p, low, mid-1, key);}}int main(){int a[1000];for (int i=0; i < 1000; i++){a[i] = i;}cout << bin_search(a, 0, 999, 185) << endl;return 0;}