C++二分查找(折半查找)递归算法详解
2023-06-13 09:11:59 时间
前面介绍过二分查找算法,以及如何使用它来查找给定值的排序数组,本节来看一看如何使用递归实现二分查找算法。
否则,如果 value 小于中间元素,则必须在原始范围的下半部分中进行查找(对同一类型的较小问题进行递归调用); 如果 value 大于中间元素,则必须在原始范围的上半部分查找;
假设要编写一个函数,其函数原型如下:
int binarySearch(const int array[], int first, int last, int value)
其中,形参 array 是要查找的数组,形参 first 保存了查找范围(即要查找的数组的一部分)中第一个元素的下标;形参 last 保存了查找范围中最后一个元素的下标;形参 value 保存了要查找的值。如果在数组中找到了 value,则该函数将返回 value 的下标,否则返回 -1。
要使用递归,则需要找到一种方法,将在已排序数组的一定范围内查找给定值的问题分解成相同类型的小问题。首先从比较 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
22174.html
html相关文章
- C++创建线程_C语言网络编程创建线程
- 猴子吃桃 -- C++ 算法
- 快速排序算法——C/C++
- C++运算符重载(二)之左移运算符重载
- 各种常用排序算法(C/C++,Java)动态显示
- c++与三菱plc通信_C语言编写的代码是
- C++基本概念_c语言 c++区别
- C++不知算法系列之排序从玩转冒泡算法开始
- C/C++ 常用加解密算法收集
- 从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下
- 字符串匹配算法KMP, BM_BC/BM_GS如何理解? C++语言
- C/C++:string类的模拟实现
- C++箴言:避免构造或析构函数中调用虚函数详解编程语言
- C++ Boost库是什么?
- C++函数重载详解
- C++ merge和inplace_merge(STL merge和inplace_merge)算法详解
- C++ find_if_not(STL find_if_not)查找算法详解
- C++ complex复数类用法详解
- VS Code运行C和C++程序
- 深入C++浮点数无效值定义与判定的解决办法
- C++类的静态成员深入解析
- C++实现图形界面时钟表盘代码
- C++取得当前时间的方法
- C++堆排序算法的实现方法
- C++实现一维向量旋转算法