二分查找（递归实现）c++

以下是C++中递归实现的二分查找的代码示例：

int binarySearch(int a[], int low, int high, int key) {
    if (low > high) {
        return -1; // 该元素不存在
    }
    
    int mid = (low + high) / 2;
    
    if (a[mid] == key) {
        return mid; // 找到了该元素，返回下标
    } else if (a[mid] > key) {
        return binarySearch(a, low, mid - 1, key); // 在左半部分继续查找
    } else {
        return binarySearch(a, mid + 1, high, key); // 在右半部分继续查找
    }
}

该函数接受一个有序数组a、数组的起始索引low、数组的结束索引high和要查找的元素key作为参数。它通过递归的方式在数组中查找元素key，并返回其下标。如果找不到该元素，则返回-1。

相关问题

二分查找递归算法c++

以下是二分查找递归算法的C语言代码：

int binarySearch(int arr[], int low, int high, int key) {
    if (high < low) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (key == arr[mid]) {
        return mid;
    } else if (key < arr[mid]) {
        return binarySearch(arr, low, mid - 1, key);
    } else {
        return binarySearch(arr, mid + 1, high, key);
    }
}

其中，arr为已排序的数组，low和high分别为数组的起始位置和结束位置，key为要查找的元素。

首先判断high是否小于low，如果是，则返回-1，表示未找到。否则，计算中间位置mid，并将key与arr[mid]进行比较。如果相等，则返回mid，表示找到了该元素。如果key小于arr[mid]，则递归查找前半部分数组，即low到mid-1位置的元素。否则，递归查找后半部分数组，即mid+1到high位置的元素。

C++递归实现二分查找

### 回答1：
好的，以下是C++递归实现二分查找的代码：

#include<iostream>
using namespace std;

int binary_search(int arr[], int low, int high, int target){
    if(low > high){
        return -1;
    }
    int mid = low + (high - low) / 2;
    if(arr[mid] == target){
        return mid;
    }
    else if(arr[mid] > target){
        return binary_search(arr, low, mid-1, target);
    }
    else{
        return binary_search(arr, mid+1, high, target);
    }
}

int main(){
    int arr[] = {1, 3, 4, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int index = binary_search(arr, 0, n-1, target);
    if(index == -1){
        cout << "Not found\n";
    }
    else{
        cout << "Found at index: " << index << endl;
    }
    return 0;
}

在上述代码中，我们通过递归的方式实现了二分查找算法。函数binary_search的四个参数分别为数组arr、搜索区间的左端点low、搜索区间的右端点high以及目标元素target。我们首先计算出搜索区间的中间位置mid，然后判断arr[mid]与target的大小关系，如果相等则说明找到了目标元素，返回mid；否则，如果arr[mid] > target，则说明目标元素在mid的左侧，递归搜索左侧区间；如果arr[mid] < target，则说明目标元素在mid的右侧，递归搜索右侧区间。如果搜索区间的左端点low大于右端点high，则说明目标元素不存在于数组中，返回-1。

### 回答2：
二分查找是一种常见的查找算法，通过将已排序的数组分成两个子数组，从而不断缩小查找范围，最终找到目标元素或确定不存在目标元素。

递归实现二分查找的思路如下：
1. 首先判断数组是否为空，如果为空则返回-1，表示未找到目标元素。
2. 确定数组的中间元素位置，可以取该子数组的中间索引值mid = (low + high) / 2。
3. 比较中间元素与目标元素的大小关系：
- 如果中间元素等于目标元素，返回中间索引值mid，表示找到了目标元素。
- 如果中间元素大于目标元素，说明目标元素在左侧子数组中，将high值更新为mid-1，继续在左侧子数组中查找。
- 如果中间元素小于目标元素，说明目标元素在右侧子数组中，将low值更新为mid+1，继续在右侧子数组中查找。
4. 重复上述步骤，直到找到目标元素或子数组长度为0为止。

递归实现二分查找的代码如下：

def binary_search(arr, low, high, target):
    if low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binary_search(arr, low, mid - 1, target)
        else:
            return binary_search(arr, mid + 1, high, target)
    else:
        return -1

使用该函数进行二分查找的示例：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 6
result = binary_search(arr, 0, len(arr) - 1, target)
if result != -1:
    print("目标元素在数组中的索引位置为:", result)
else:
    print("目标元素不存在数组中")

以上就是用递归实现二分查找的方法和示例。

### 回答3：
二分查找是一种基于分治思想的查找算法，递归实现二分查找的步骤如下：

1. 定义一个递归函数，传入要查找的数组、要查找的元素、数组的左边界和右边界四个参数。
2. 判断左边界是否大于右边界，若是则表示无法再继续查找，返回-1表示查找失败。
3. 计算数组的中间位置，可以使用 (左边界 + 右边界) / 2 进行计算。
4. 比较中间位置的元素与要查找的元素的大小关系：
- 若中间位置的元素等于要查找的元素，则返回中间位置。
- 若中间位置的元素大于要查找的元素，则在左边的子数组中继续查找，更新右边界为中间位置-1，递归调用函数。
- 若中间位置的元素小于要查找的元素，则在右边的子数组中继续查找，更新左边界为中间位置+1，递归调用函数。
5. 重复以上步骤，直至查找成功或查找失败。

以下是递归实现二分查找的示例代码：

def binary_search(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target, 0, len(arr) - 1)
if result != -1:
    print("元素在数组中的索引为", result)
else:
    print("未找到元素")

以上就是用递归实现二分查找的方法。递归是一种灵活而强大的编程技巧，在处理分治问题时能够简化代码逻辑，但需要注意递归的退出条件和参数的传递。