Блог

 #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;
}
 

Как я могу разбить рекурсивный?

Это поиск разделов, который не отсортирован, но когда он нашел рекурсивный ответ, не останавливающий его, приводит к неправильному ответу.

Вы забываете использовать результат ваших рекурсивных вызовов, это должно быть что-то вроде:

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

        if (int res = find(a, l, mid - 1, value); res != -1) { return res; }
        if (int res = find(a, mid   1, r, value); res != -1) { return res; }
    }
    return -1; // Not found
}
 

Вы забыли поставить 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 resu<
    }

    return -1;
}
 

Но в этом случае ваш поиск всегда будет сначала искать левую сторону, что в точности соответствует линейному поиску.