CODEWITHSUNDEEP
crecursionbinary-search
Ezrb3zr
Ezrb3zr

Reputation: 81

Binary Search Recursion Algorithm Issue In C

Ok, so I'm given the function 

int bin(int value, int size, int array[])

I am supposed to find "value" within "array[]", but the issue at hand here is that in most cases, we have something along the lines of 

int bin(int value, int max, int min, int array[])

The recursion, logically, is a lot easier on this part due to the fact I can still pass the number I am at, as well as remember the size of the array.

int bin(int array[], int value, int min, int max)
{
    if(max < min)
        return -1;
    else
    {
        int mid = min + (max - min)/2;

        if(array[mid] > value)
            return bin(array, value, min, mid-1);
        else if(array[mid] < value)
            return bin(array, value, mid+1, max);
        else
            return mid;
    }

But since I can only pass 1 integer, how exactly would I adjust this algorithm for it? In essence, I would only be able to do something like this, but I KNOW it will not logically work. Is there a way, though, that I can see the size of the array? I tried it, but the numbers weren't crunching right.

   int bin(int array[], int value, int size)
    {
            int mid = size/2;

            if(array[mid] > value)
                return bin(array, value, size-(size/2));
            else if(array[mid] < value)
                return bin(array, value, size+(size/2));
            else
                return mid;
    }

Upvotes: 4

Views: 2212

Answers (3)

user3102756
user3102756

Reputation: 1

int * binSearch (int *arr,int size, int num2Search)

{

    if(size==1)

        return ((*arr==num2Search)?(arr):(NULL));

    if(*(arr+(size/2))<num2Search)

        return binSearch(arr+(size/2)+1,(size/2),num2Search);

    if(*(arr+(size/2))==num2Search)

        return (arr+(size/2));

    return binSearch(arr,(size/2),num2Search);

}

in my function, you get the same parameters and return the adress of the value.

Upvotes: 0

Brian J
Brian J

Reputation: 694

The purpose of having a method with a different argument set is to make the method easy to call for the user. This is very common in recursion.

There is the public method that is available to the user that has the
int bin(int value, int size, int array[]) signature.

There should then be the private, internal helper method with the
int bin(int value, int max, int min, int array[]) signature.

The point is, someone calling this method will want to pass in the size of the array, and not the start and end index (because to them, the start index should always be 0, end should always be size-1) and it is bad practice to have a method with arguments that are preset like that.

The helper method with the start and end values (min and max) is used in the recursive calls for more efficient computations, and it hides the unnecessary arguments from the user.

Your method should then look something like this:

int bin(int value, int size, int array[]) {
    return bin(value, size - 1, 0, array);
}

Upvotes: 0

tbert
tbert

Reputation: 2097

You need to explicitly pass the base as well:

int
bin(int array[], int value, int size)
{
        int mid = size/2;

        if(array[mid] > value)
            return bin(array, value, size/2);
        else if(array[mid] < value)
            return bin(&array[mid], value, size/2);
        else
            return mid;
}

note the "&array[mid] in the "if(array[mid] < value)" case

each time, you have the correct half of the array to search, using base + offset vice min/max indices

Upvotes: 13

Related Questions