二分查找递归算法源码
时间: 2024-06-30 12:00:24 浏览: 157
二分查找(也称为折半查找)是一种在有序数组中查找特定元素的搜索算法,通过将数组一分为二来减少搜索范围。递归版本的二分查找源码通常如下:
```cpp
// 假设数组 `arr` 已经排序
int binarySearchRecursive(int arr[], int low, int high, int target) {
// 基本情况:如果低索引大于或等于高索引,说明没有找到目标
if (low > high)
return -1; // 返回-1表示未找到
// 计算中间索引
int mid = low + (high - low) / 2;
// 如果中间元素等于目标,返回其索引
if (arr[mid] == target)
return mid;
// 如果目标小于中间元素,则在左半部分继续查找
if (arr[mid] > target)
return binarySearchRecursive(arr, low, mid - 1, target);
// 否则,在右半部分查找
else
return binarySearchRecursive(arr, mid + 1, high, target);
}
// 使用时调用:
int result = binarySearchRecursive(arr, 0, arr.length - 1, target);
```
相关问题
二分查找递归算法源码c语言
二分查找递归算法是一种在有序数组中查找特定元素的有效方法。它通过将数组分成两半并确定目标值可能在哪一半,然后继续这个过程,直到找到目标或确定它不存在。以下是二分查找递归算法的C语言源代码示例:
```c
#include <stdio.h>
// 二分查找函数(递归)
int binarySearch(int arr[], int low, int high, int target) {
if (high >= low) {
int mid = low + (high - low) / 2; // 计算中间索引
// 如果目标值等于中间元素
if (arr[mid] == target)
return mid;
// 如果目标值小于中间元素,则在左半部分继续查找
else if (arr[mid] > target)
return binarySearch(arr, low, mid - 1, target);
// 否则,在右半部分查找
else
return binarySearch(arr, mid + 1, high, target);
}
// 如果未找到目标,返回 -1 表示元素不存在
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40}; // 示例数组,已排序
int size = sizeof(arr) / sizeof(arr);
int target = 10; // 要查找的元素
int result = binarySearch(arr, 0, size - 1, target);
if (result != -1)
printf("元素在数组中的索引为: %d\n", result);
else
printf("元素不在数组中。\n");
return 0;
}
```
数据结构查找算法源码
数据结构中的查找算法主要包括线性查找和二分查找两种。其中,线性查找适用于无序表,时间复杂度为O(n);而二分查找适用于有序表,时间复杂度为O(logn)。
下面是二分查找的C++源码示例:
```c++
int binarySearch(int arr[], int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
```
上述代码中,二分查找函数 `binarySearch` 的参数依次为:待查找数组 `arr`、左边界 `left`、右边界 `right`、目标值 `target`。函数内部使用递归实现二分查找,当左边界大于右边界时,表明未找到目标值,返回-1;若中间值等于目标值,则返回中间值下标;否则,若中间值大于目标值,则在左半部分继续查找;若中间值小于目标值,则在右半部分继续查找。