递归算法实现二分查找C++.docx
需积分: 1 181 浏览量
2023-09-17
13:57:04
上传
评论
收藏 16KB DOCX 举报
使用 C++语言实现的递归二分查找算法的示例代码：
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int target, int left, int right) {
if (left > right) {
return -1; // 未找到目标元素
}
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // 找到目标元素
} else if (nums[mid] < target) {
return binarySearch(nums, target, mid + 1, right); // 在右半部分继续查找
} else {
return binarySearch(nums, target, left, mid - 1); // 在左半部分继续查找
}
}
int main() {
vector<int> nums = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int index = binarySearch(nums, target, 0, nums.size() - 1);
if (index != -1) {
cout << "目标元素 " << target << " 的索引是 " << index << endl;
} else {
cout << "未找到目标元素 " << target << endl;
}
return 0;
}
在上面的代码中，我们定义了一个名为 binarySearch 的递归函数，该函数接受一个有序整
数数组 nums、目标元素 target 以及搜索范围的左右边界 left 和 right 作为参数。
在递归函数中，首先判断如果左边界大于右边界，说明未找到目标元素，返回-1。然后，
计算中间元素的索引 mid，并与目标元素进行比较。如果中间元素等于目标元素，返回中
间元素的索引。如果中间元素小于目标元素，说明目标元素在右半部分，继续在右半部分
递归调用 binarySearch 函数。如果中间元素大于目标元素，说明目标元素在左半部分，继
续在左半部分递归调用 binarySearch 函数。
资源评论
