CODEWITHSUNDEEP
cbinary-search
NotInCheck
NotInCheck

Reputation: 21

Binary Search dosen't find the right value

I create a vector with 1000 elements, the value of the elements is the index itself V[100] = 100, V[50] = 50 etc.

When I call the binary search by the value it must return to me the index, what is itself so binary_search(vector, begin, end, 50) must returns to me 50, but returns 30. I tried to debug with gdb, but can't find anything wrong.

Code:

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

Upvotes: 2

Views: 125

Answers (4)

Bunny
Bunny

Reputation: 11

U Can Use this Code and your Code is also correct but you should use else if statements while comparing......

Have A Great Day Enjoy Coding

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

}

Upvotes: -1

Vincenzo Greco
Vincenzo Greco

Reputation: 21

The problem is in the return. When the function returns it doesn't end and continue calling other if statement changing the mid variable. You can change like this


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

Upvotes: -1

Vikash Kesarwani
Vikash Kesarwani

Reputation: 850

Problem with your code is that you are not returning the value from the recursive call if rbb function. You should modify your code 

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);

Upvotes: 4

K.D.Gayan
K.D.Gayan

Reputation: 243

you can try this

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

Upvotes: 0

Related Questions