欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找的递归实现

程序员文章站 2024-03-20 10:24:40
...

二分查找一般都是使用迭代实现,就想到使用递归实现一下二分查找,代码如下(不是领扣里的题)。

#include<vector>
#include<iostream>

using namespace std;

// 从下标start~end的数组查找target,成功返回下标,失败返回-1
int find(vector<int>arr, int start, int end, int target);

int main(){
    vector<int> arr;
    for(int i=0; i<200; i+=2){
        arr.push_back(i);
    }
    // 查找
    int target;
    while(1){
        cout<<"输入需要查询的数字 :";cin>>target;
        cout<<"数字"<<target<<"位于数组的第"<<find(arr,0,99,target)<<"位\n";
    }
    return 0;
}

int find(vector<int>arr, int start, int end, int target){
    int mid = (start+end)/2;
    // 查找失败
    if(start>end){
        return -1;
    }
    if(arr[mid] == target){
        return mid;
    }
    arr[mid]>target?(end=mid-1):(start=mid+1);
    return find(arr,start,end,target);
}