【C++】递归之二分查找

发布时间：2020-12-14 04:38:10 所属栏目：百科来源：网络整理

导读：简单查找的时间复杂度为 O(n) 二分查找的时间复杂度为 O(logn) 用递归实现二分查找：基线条件：数组只包含一个元素。如果如果要查找的值与这个元素相同，就找到了；否则说明不在数组中。递归条件：把数组分成两半，将其中一半丢弃，并对另一半执行二分

简单查找的时间复杂度为O(n)

二分查找的时间复杂度为O(logn)

用递归实现二分查找：

　　基线条件：数组只包含一个元素。如果如果要查找的值与这个元素相同，就找到了；否则说明不在数组中。

　　递归条件：把数组分成两半，将其中一半丢弃，并对另一半执行二分查找。

C++代码实现如下（VS可以直接运行）：

#include <iostream>

using namespace std;

//x为目标数据、left为数组第一个元素下标、right为数组最后一个元素下标
int recurBinarySearch(int* p,int x,1)">int left,1)">int right);

 main()
{
    int array[] = { 0,1,1)">2,1)">3,1)">4,1)">5,1)">6,1)">7,1)">8,1)">9 };
    int x = 7;
     result;
    result = recurBinarySearch(array,x,1)">);
    if (result == -1)
        cout << "没找到" << endl;
    else
        cout << 在array[" << result << ]里找到" << x << endl;
}

 right)
{
    基线条件
    if (left == right)
        return left;

    递归条件
    if (left < right)
    {
        int mid = (left + right) / 2;  得到中间值
        if (x < p[mid])  小于，改变right
            return recurBinarySearch(p,left,mid - );
        else if (x > p[mid])  大于，改变left
            ,right);
        else
            return mid;  得到x
    }
    return -;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!