Binary search using recursion...don't know what I am doing wrong

I need to write a recursive function to perform a binary search on an array of 30.

This is what I got so far, I think I have done everything correctly, but I can't see the error in the code.

Code:

---

int find_array(int a[], int left, int right, int elem);

int main ()
{
        int a[] = {
        1,        4,        6,        8,        9,        10,        13,        16,        17,        19,
        20,        21,        30,        32,        33,        35,        37,        39,        50,        70,
        71,        73,        79,        81,        85,        87,        95,        96,        97,        99 };


        int size = sizeof(a) / sizeof(int);

        int num, index;

        while (num != 0)
        {
                printf("Enter a positive number: ");
                scanf("%d", &num);

                if (num == 0)
                {
                        ;
                }

                else
                {

                        index = find_array(a, 0, size-1, num);

                        if (index == -1)
                        {
                                printf("%d is not included\n", num);
                        }

                        else
                        {
                                printf("%d is at index %d\n", num, index);
                        }
                }
        }
        return 0;
}

int find_array(int a[], int left, int right, int elem)
{
        int middle;

        if (left > right)
        {
                return -1;
        }

        else
        {
                middle = left + (right-left) / 2;

                if (elem == a[middle])
                {
                        return middle;
                }

                else
                {
                        if (elem < a[middle])
                        {
                                find_array(a, 0, middle-1, elem);
                        }

                        else
                        {
                        find_array(a, middle+1, right, elem);
                        }
                }
        }
}

---

Please help, thanks.

Code:

---

find_array(a, 0, middle-1, elem);

---

You shouldn't be hard coding the value '0' in your find function. It should be 'left' instead of '0'.

Quzah.

Thanks, the problem is that index is giving me the value "2008958736" for each positive value I enter. I have no iedea where that number is coming from, what I do know is that something is wrong, but I don't believe I have done something wrong...at least I can't see it. I'm new in C btw...

You need to be returning a value at every step in the program. Walk through your program:

Code:

---

int find_array( ... )
{
        if( left > right )
                return -1;
        else
        {
                middle = left + (right-left) / 2;

                if (elem == a[middle])
                {
                        return middle;
                }
                else
                {
                        if (elem < a[middle])
                        {
                                find_array(a, 0, middle-1, elem);
                        }
                        else
                        {
                        find_array(a, middle+1, right, elem);
                        }
                }
        }
        /* Uh oh! We get here with nothing returned! */
}

---

Walk through this with the following array:

Code:

---

array[] = { 1, 2, 3 }

index = find_array( ... 2 );

---

We're trying to find 2 here.
Running through your program:

Code:

---

    left is not greater than right, so don't return -1
    if elm is what we're looking for, return it, it isn't ,so we continue

    we have a recursive call now, the return value of which is discarded

        we're in the first recursive call
        the -1 check passes, so we keep going
        this slot is what we're looking for, so we return it

    we now have exited the recursive call
    the value we just returned was discarded
    we now drop out of all } } } } lines
    we reach the end of the function, nothing is returned[

---

Actually something is returned, but it's some undefined piece of memory, which is why you get what you get.

You should modify your recursive calls to something like:

return find_array(a, middle+1, right, elem);

Just remember this key thought: Whenever a function exits, if it is a non-void function, it must return something.

Your compiler should be warning you about reaching the end of a function and not returning something. Pay attention to your compiler.

Quzah.

Thanks a lot! :)

I'll remember your tips and advice! :)