Бинарный поиск не нашел правильное значение

Question

Я создаю вектор с 1000 элементами, значением элементов является сам индекс V [100] = 100, V [50] = 50 и т. Д.

Когда я вызываю двоичный поиск по значениюон должен вернуть мне индекс, что само по себе так двоичный_поиск (вектор, начало, конец, 50) должен вернуть мне 50, но возвращает 30. Я попытался отладить с помощью GDB, но не могу найти ничего неправильного.

Код:

int rbb(int *v, int left, int right, int val) 
{

    int mid = (left + right) / 2;  //middle element

    if (right < left) //stop codition, pointers shifted
        return -1;

    if (val == v[mid]) //found value
        return mid;  

    if (val > v[mid]) //value is on vector right portion
        rbb(v, mid+1, right, val);

    if (val < v[mid]) //value is on vector left portion
        rbb(v, left, mid-1, val);

}

int main () 
{

    int v[1000];

    for (int i = 0; i < 1000; i++)
        v[i] = i;

    int x = rbb(v, 0, 999, 300);
    printf("%d", x);
}

Answer 1

Проблема с вашим кодом в том, что вы не возвращаете значение из рекурсивного вызова, если функция rbb. Вы должны изменить свой код

if (val > v[mid]) //value is on vector right portion
    return rbb(v, mid+1, right, val);

if (val < v[mid]) //value is on vector left portion
    return rbb(v, left, mid-1, val);

Answer 2

U можете использовать этот код, и ваш код также является правильным, но вы должны использовать другое, если утверждения при сравнении ......

Хорошего дня Наслаждайтесь кодированием

#include<stdio.h>
int rbb(int v[], int left, int right, int val);
int main ()
{
int i,v[1000],x;
   for (i = 0; i <1000; i++)
     {
        v[i] = i;
     }
     x = rbb(v, 0,999, 300);
     printf("%d", x);

}
int rbb(int v[], int left, int right, int val) {
int mid;
mid = (left + right) / 2;  //middle element
if (right < left) //stop codition, pointers shifted
   {
      return 1;
   }
else if (val == v[mid]) //found value
   {    
      return mid;
   }
else if (val > v[mid]) //value is on vector right portion
    {
        rbb(v, mid+1, right, val);
    }
else//value is on vector left portion
    {
        rbb(v, left, mid-1, val);
    }

}

Answer 3

Проблема в возврате. Когда функция возвращается, она не заканчивается и продолжает вызывать оператор if, изменяющий переменную mid. Вы можете изменить как это

    int rbb (int *v, int left, int right, int val){
        int mid = (left + right) / 2;  //middle element

        if (right < left) //stop codition, pointers shifted
            return -1;

        else if (val == v[mid]) //found value
            return mid;

        else if (val > v[mid]) //value is on vector right portion
            rbb(v, mid+1, right, val);

        else if (val < v[mid]) //value is on vector left portion
            rbb(v, left, mid-1, val);
    }

    int main() {
        int v[1000];

        for (int i = 0; i < 1000; i++)
            v[i] = i;

        int x = rbb(v, 0, 999, 300);
        printf("%d", x);
    }

Answer 4

Вы можете попробовать это

int rbb(int *v, int left, int right, int val) {

int mid = (left + right) / 2;  //middle element

if (right < left) //stop codition, pointers shifted
    return -1;

èlse if (val == v[mid]) //found value
    return mid;  

else if (val > v[mid]) //value is on vector right portion
    rbb(v, mid+1, right, val);

else if (val < v[mid]) //value is on vector left portion
    rbb(v, left, mid-1, val);
}

int main () {

int v[1000];

for (int i = 0; i < 1000; i++)
    v[i] = i;

int x = rbb(v, 0, 999, 300);
printf("%d", x);
}