时间戳

首页 > 解决方案 > 如何为未排序的分区搜索中断递归

c++ - 如何为未排序的分区搜索中断递归

问题描述

#include <iostream>

int find(int *a, int l, int r, int value)
{
    if (l <= r)
    {
        int mid=(l + r) / 2;
        if (a[mid] == value) 
          return mid;
        find(a, l, mid-1, value);
        find(a, mid+1, r, value);
    }
    return -1;
}

int main()
{
    int a[30] = {1,3,5,7,9,12,25,56,90,81,101,
               106,120,130,4,6,200,17,18,19,20,
               12,456,4325,6507,59,69,58,384,299};
    int size = 30;
    int k = 3;
    int pos = -1;
    std::cout << "Can find " << k << " in position " << find(a, 0, size - 1, k) << "\n";
    return 0;
}

我怎样才能打破递归？

这是未排序的分区搜索，但是当它发现答案递归时不会停止它会导致错误答案。

标签： c++

解决方案

您忘记在递归调用之前输入 return ：

int find(const int *a,const int l,const int r,const int value)
{
    if(l<=r)
    {
        const int mid=(l+r)/2;
        if(a[mid]== value) 
            return mid;
        const int result = find(a,l,mid-1,value);
        if (result == -1)
            return find(a,mid+1,r,value);
        else
            return result;
    }

    return -1;
}

但在这种情况下，您的搜索将始终先搜索左侧，这与线性搜索完全相同。

推荐阅读