首页 > 编程笔记 > C++笔记 阅读:615

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

C语言/C++交流群:664104694(我们会不定期在群内分享编程知识,上传编程资料)

编程帮,一个分享编程知识的公众号。跟着站长一起学习,每天都有进步。

通俗易懂,深入浅出,一篇文章只讲一个知识点。

文章不深奥,不需要钻研,在公交、在地铁、在厕所都可以阅读,随时随地涨姿势。

文章不涉及代码,不烧脑细胞,人人都可以学习。

当你决定关注「编程帮」,你已然超越了90%的程序员!

编程帮二维码
微信扫描二维码关注