Recursive function for Binary Search

[LibLife]

So I am writing a a recursive function to do a binary search. I have managed to make my program run, but it is not doing what I want it to do. For some numbers, it tells me "Number is not found" even though the number is in the list.

I just can't figure out the problem. Please help me.
Thank you,

  #include <iostream>
using namespace std;

int BinarySearch(int list[], int low, int high, int key);


int main()
{
    int Array[] = {1, 3, 4, 6, 9, 10, 14, 19, 23, 30};
    int first = 0;
    int last = 9;
    int value;

    for( int i= 0; i< 10; i++)
    {
        cout << "{" <<Array[i] <<" "<<"}";
    }
    cout << "\n\nPlease enter a number to find from the above list of number. \n";
    cin >> value;
    cout << "\n\n";

    int Location = BinarySearch(Array, first, last, value);

    if(Location==-1)
         cout<< "Number is not found.\n";
    else
         cout<< "Number is found.\n";
    return 0;
}

int BinarySearch(int list[], int low, int high, int key)
{
    int mid=(high + low)/2;

    if(low<=high)
    {
        if (list[mid] == key)
        {
        return mid;
        }
        else if (list[mid] >key)
            return BinarySearch(list,low,mid -1, key);
        else
            return BinarySearch(list,high,mid + 1, key);
    }
    else return -1;
}

[D80DSL3A]

2 errors I see.
It looks as if the function was written for arrays sorted in descending order (high to low). Look at line 42. It says look further left for higher values. Lower values are to the left in your ascending ordered array. So, for line 41 try:
else if (list[mid] <key)
I also think you have lo and high arguments reversed on line 44. New lo is mid+1, not high.
Try: return BinarySearch(list,mid + 1,high, key);

Your return value at the end may be an issue. I think once you reach low==high, you have found the element, or not. Check and return -1 only if key not found at list[low]

if( low < high )// actually. exclude = case. Done if =
{
    // haven't zeroed in on key yet. Keep going
}
// now low == high
if( list[low] == key ) return low;
else return -1;

[LibLife]

Thank you!

So I worked and it looks good, but now my compiler keeps saying "Program has stopped working." I don't know if it's a problem with just this code, but the compiler runs fine with a other codes.

#include <iostream>
using namespace std;

int BinarySearch(int list[], int low, int high, int key);


int main()
{
    int SIZE;
    int Array[SIZE];
    int value;

    cout << "Please enter the size of your array. \n";
    cin >> SIZE;
    cout<< "\n";

    cout << "Please enter the numbers of your array. \n";
    for(int i= 0; i< SIZE; i++)
        {
            cout << "Element #" <<i+1 <<": ";
            cin>> Array[i];
        }
    cout << "\nPlease enter a number to find from the above list of numbers. \n";
    cin >> value;
    cout << "\n\n";

    int Loc = BinarySearch(Array, 0, SIZE- 1, value);

    if(Loc >= 0)
        {
        cout<< "Number is not found.\n";
        cout << "The number is: " <<Loc +1 << ".\n";
        }
        else
            cout<< "Number is found.\n";

    return 0;
}

int BinarySearch(int list[], int low, int high, int key)
{
    if(low > high)
    {
        return -1;
    }
    int mid= low + (high - low)/2;

        if (list[mid] == key)
        {
            return mid;
        }
        else if (list[mid] <key)
            return BinarySearch(list,low,mid -1, key);
        else
            return BinarySearch(list,mid + 1, high, key);
}

[Chervil]

So I worked and it looks good, but now my compiler keeps saying "Program has stopped working." I don't know if it's a problem with just this code, but the compiler runs fine with a other codes.

That message is not from the compiler, it's a run-time error.

There are errors in the code. Compiled as standard C++ it fails to compile because it is attempting to use variable-length arrays which are not valid in C++. (Most likely you are using some non-standard compiler extension).
This is the error message from my compiler:

[Error] ISO C++ forbids variable length array 'Array' [-Wvla]

at line 10:

    int SIZE;              // uninitialised variable
    int Array[SIZE];       // SIZE must be a constant, not a variable 

The other problem is that the variable SIZE is not initialised - it contains garbage.

Later in the program, you ask the user to supply a value for SIZE, but by that time it is too late, the garbage value has already been used.

If you use g++ compiler, use (at least) these compiler options:

-std=c++11 -Wextra  -Wall -pedantic-errors

so that the compiler will tell you about such problems with the code.



Solutions
1. Simplest. Declare an array of a fixed size, say 100. Make sure that the user supplied size is no greater than this fixed size.

2. Use dynamic allocation with new [] and delete []. This is a more powerful approach, but it may be a distraction in the current situation.

3. Use a C++ std::vector<int>. Probably even better, but would require some reworking of other code. Maybe leave this for now even though it is a good solution.

[jgg2002]

Depends on what compiler you are using and if there are any extensions. My guess is that there are such extensions on your compiler for variable sized arrays. Try doing the following when you declare & read size.

int SIZE=0;
cin>>SIZE;
int Array[SIZE];

[D80DSL3A]

OK. I hadn't noticed the variable sized array issue and that is going to cause problems.

Your changes to BinarySearch weren't what I had in mind.
This is what I was thinking:

int BinarySearch(int list[], int low, int high, int key)
{
    if(low < high)
    {
        int mid=(high + low)/2;
        if (list[mid] == key)
            return mid;
        else if (list[mid] > key)// this was correct after all
            return BinarySearch(list,low,mid -1, key);
        else
            return BinarySearch(list,mid + 1,high, key);// was error here
    }
    else if(list[low] == key) return key;// found key
    else return -1;// key not found
}

[Chervil]

return mid; // line 7
and
return key; // line 13
are returning different kinds of animals.
mid is an array subscript, but key is an element in the array (if found).

[D80DSL3A]

Thank you. That is a silly error.
Line 13 should be: else if(list[low] == key) return low;// found key at element low

[Chervil]

No problem.
By the way, that version seems to work, and so does the most recent version posted by LibLife. (though I changed the < operator to > at line 52, to suit the sort order of my test data).

[LibLife]

Thanks mates!
I got it to run fine.