二分查找递归实现--【编程珠玑】

作者说 有百分之九十的程序员在程序中发现了bug（同时怀疑那些没有发现bug的正确性）

所以尽管二分查找是我们感觉上比较简单的一个程序，但是我们依然不可小视；

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

要求是数组有序，当然，若是无序的话排序即可（升序或降序无所谓，例子中是有序的）；

有了主要思想，下面贴出代码（我也不能保证我不是那90%的人之一，欢迎提点）：

#include <iostream>
#include <cstring>

using namespace std;

int BinarySearch(int s[], int x, int low, int high)
{
    if( high < low) return -1;  //找不到
    int middle = (low + high) / 2;  //二分
    if( x == s[middle]) return middle;  //找到并返回
    else if( x < s[middle])  //关键字小于中值，继续二分查找，并将上限改为middle
       BinarySearch(s, x, low, middle - 1);
    else                     //关键字大于中值，继续二分查找，并将下限改为middle
       BinarySearch(s, x, middle + 1, high);
}

int main()
{
    int s[] = {0, 3, 5, 7, 11, 14, 16, 34, 50, 65, 70}; //递增序列，也可运用动态数组存数据

    cout<<"请输入需要查找的数：";
    int num;
    cin>>num;

    int n = sizeof(s) / sizeof(int);

    int index = BinarySearch(s, num, 0, n - 1);
    if(index >= 0)  //根据返回值判断是否在数组中
       cout<<"数字"<<num<<"在数组第"<<index + 1<<"个"<<endl;
    else
       cout<<"数字"<<num<<"不在数组中"<<endl;
    return 0;
}

试运行：

祝大家在新的一年里 学有所成 工作顺利

欢迎指点，o(∩_∩)o