Recursive function for a binary search in C++

Question

Create a recursive function for the binary search. This function accepts a sorted array and a give item being search for and returns the index of the item if this give item in the array or returns -1 if this give item is not in the array. Moreover, write a test program to test your function.

Sorry for the bad english but my teacher can not write it or speak it very well. This is for a final project and determines whether I graduate or not I went to the tutor and he did not know how to do it either. Any help is greatly appreicated.

template int orderedArrayListType::binarysearch (const elemType& item) const

{

int first= 0;
int last = length -1;
int mid;
int list[];
int BinarySearch(,Type & Item, int first, int last)
bool found = false;

while (first <= last && !found)

{

    mid = (first + last) / 2;

    if (list[mid] > item)
        return BinarySearch(list, item, first, mid -1)

    found = true;

    else if (list[mid] > item)
        return BinarySearch( list, item, first, mid -1)
        last = mid - 1;
    else 
        first = mid + 1;

}

if (found)

    return mid;
else 
    return -1;

}//end Binary Search

Answer 1

Just use std::binary_search. Tell the tutor that function is actually implemented recursively in your_favorite_compiler.

Answer 2

You could also google "recursive binary search" and voila!

EDIT- Wikipedia knows all (especially when it comes to cs):

The most straightforward implementation [of the binary search algorithm] is recursive, which recursively searches the subrange dictated by the comparison:

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2) 
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

Answer 3

There's a child's game in the USA where one child picks a number between 1 and 10, and the other child has to guess that number. If they guess wrong, the first child says "higher" or "lower".

Most kids start out guessing randomly, and will take about 4-5 tries on average to succeed. I realized (and this is probably why I ended up in computer science), that the best thing to do is pick the mid point (5.5, so pick either 5 or 6. I'll go with 5.). Based on what they say ("higher" or "lower"), select a new range, either 1-4 or 6-10. Pick the number in the middle of that range (2 or 8). Keep splitting the range in half until you get the number.

That's a binary search on a sorted array (the sorted array being numbers from 1 to 10).

To implement that in code, just keep doing the same process described above. Pick the midpoint of the range, and create a new range based on the answer.

Here's one solution in Java that does this recurvively.