C++二分查找（折半查找）递归算法详解

前面介绍过二分查找算法，以及如何使用它来查找给定值的排序数组，本节来看一看如何使用递归实现二分查找算法。

假设要编写一个函数，其函数原型如下：

int binarySearch(const int array[], int first, int last, int value)

其中，形参 array 是要查找的数组，形参 first 保存了查找范围（即要查找的数组的一部分）中第一个元素的下标；形参 last 保存了查找范围中最后一个元素的下标；形参 value 保存了要查找的值。如果在数组中找到了 value，则该函数将返回 value 的下标，否则返回 -1。

要使用递归，则需要找到一种方法，将在已排序数组的一定范围内查找给定值的问题分解成相同类型的小问题。首先从比较 value 与查找范围的中间元素开始：

• 如果 value 等于中间元素，则查找完成，立即返回中间元素的下标；
• 否则，如果 value 小于中间元素，则必须在原始范围的下半部分中进行查找（对同一类型的较小问题进行递归调用）；
• 如果 value 大于中间元素，则必须在原始范围的上半部分查找；

请注意，每次进行递归调用时，查找范围都会变小。基本情况是当查找范围为空时。以下是该函数代码：

int binarySearch(const int array[], int first, int last, int value)
{
    int middle;    //查找的中间点
    if (first > last)    // 基本情况
        return -1;
    middle = (first + last) / 2;
    if (array[middle] == value)
        return middle;
    if (array[middle] < value)
        return binarySearch(array, middle+1,last,value);
    else
        return binarySearch(array, first,middle-1,value);
}

下面的程序演示了该函数：

//This program demonstrates a recursive function that performs a binary search on an integer array.
#include <iostream>
using namespace std;

//Function prototype

int binarySearch(const int array[], int first, int last, int value);
const int SIZE = 20;

int main()
{
    int tests[SIZE] = {101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600};
    int result; // Result of the search
    int empID; // What to search for
    cout << "Enter the Employee ID you wish to search for: ";
    cin >> empID;
    result = binarySearch(tests, 0, SIZE-1, empID);
    if (result == -1)
        cout << "That number does not exist in the array.\n";
    else {
        cout << "That ID is found at element " << result;
        cout << " in the array\n";
    }
    return 0;
}
int binarySearch(const int array[], int first, int last, int value)
{
    int middle;    // Mid point of search
    if (first > last) // Base case
        return -1;
    middle = (first + last)/2;
    if (array[middle]==value)
        return middle;
    if (array[middle]<value)
        return binarySearch(array, middle+1,last,value);
    else
        return binarySearch (array, first,middle-1, value);
}

程序输出结果：

Enter the Employee ID you wish to search for: 521
That ID is found at element 17 in the array