用C++实现:给定一个升序排列的整数数组和一个目标值,编写一个递归函数,在数组中查找目标值,并返回其索引。如果目标值不存在于数组中,返回 -1。提示:可以使用二分查找的思想,每次将查找范围缩小一半,直到找到目标值或确定其不存在。
时间: 2024-10-27 18:08:32 浏览: 20
C++实现查找二叉树中和为某一值的所有路径的示例
在C++中,你可以通过递归的方式实现二分查找算法来解决这个问题。下面是一个简单的递归函数示例:
```cpp
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int target, int left = 0, int right = 0) {
// 如果左指针大于等于右指针,则表示未找到目标值,返回 -1
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, left, mid - 1); // 目标小于中间元素,向左搜索
else
return binarySearch(nums, target, mid + 1, right); // 目标大于中间元素,向右搜索
}
```
在这个函数中,`nums` 是输入的整数数组,`target` 是你要查找的目标值,`left` 和 `right` 分别代表当前搜索范围的起始和结束位置。每一步都将搜索范围缩小一半,直到找到目标或确认它不存在。
阅读全文