Binary Search Recursion Algorithm Issue In C

Question

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

please adjust your tags for 'homework' etc; your constraints sure sound like that. A hint: in C arrays are in fact pointers to the underlying datatype. So you can pass a calculated parameter 'array' to the function. — Adriaan
– Adriaan, Commented Aug 13, 2012 at 11:55
@Adriaan: Arrays aren't pointers. Arrays are arrays. However, you cannot pass arrays as function arguments, and in that context, arrays decay to pointers to the first element. That doesn't change the nature of arrays, though. — Kerrek SB
– Kerrek SB, Commented Aug 13, 2012 at 12:00

tbert · Accepted Answer · 2012-08-13 12:17:09Z

13

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

edited Aug 13, 2012 at 12:17

answered Aug 13, 2012 at 11:50

tbert

2,11713 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

tbert Over a year ago

@erturne good catch; my code still doesn't fix all of the issues(odd/even number of elements in the array, for example), but the basic idea is there

Ezrb3zr Over a year ago

Yeah. It worked. Thanks! Yeah, sometimes there are these oddball constraints in some of my Professor's programs.

Brian J Over a year ago

@Ezrb3zr This requirement for a method with a different signature is very common in recursion. There is usually a public method, and then a private helper method. I have more information about it in my answer.

tbert Over a year ago

@Ezrb3zr hey, can you accept/upvote? It's a bit rude to say that I solved your problem, but to then just leave it at that.

Jim Balter Over a year ago

Bad buggy answer should not be accepted. new size should be mid in the first case and size - mid in the second.

|

Brian J · Accepted Answer · 2012-08-13 21:01:14Z

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

TLama · Accepted Answer · 2013-12-14 18:00:14Z

0

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.

edited Dec 14, 2013 at 18:00

TLama

76.9k17 gold badges226 silver badges418 bronze badges

answered Dec 14, 2013 at 17:38

user3102756

1

Collectives™ on Stack Overflow

Binary Search Recursion Algorithm Issue In C

3 Answers 3

8 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related