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 arrayn";
    }
    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