c++ - 二分查找的递归函数

Question

为二分搜索创建一个递归函数。
这个函数接受一个排序数组和一个要搜索的项目，并返回项目的索引（如果项目在数组中），或者返回-1（如果项目不在数组中）。
此外，编写一个测试程序来测试您的功能。

template <class elemType>
int orderedArrayListType<elemType>::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;
}

Answer 1

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:

public class BinarySearchRecursive
{
    public static final int NOT_FOUND = -1;

    /**
     * Performs the standard binary search
     * using two comparisons per level.
     * This is a driver that calls the recursive method.
     * @return index where item is found or NOT_FOUND if not found.
     */
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        return binarySearch( a, x, 0, a.length -1 );
    }

    /**
     * Hidden recursive routine.
     */
    private static int binarySearch( Comparable [ ] a, Comparable x,
                                     int low, int high )
    {
        if( low > high )
            return NOT_FOUND;

        int mid = ( low + high ) / 2;

        if( a[ mid ].compareTo( x ) < 0 )
            return binarySearch( a, x, mid + 1, high );
        else if( a[ mid ].compareTo( x ) > 0 )
            return binarySearch( a, x, low, mid - 1 );
        else
            return mid;
    }

    // Test program
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [ ] a = new Integer [ SIZE ];


    for( int i = 0; i < SIZE; i++ )
        a[ i ] = new Integer( i * 2 );

    for( int i = 0; i < SIZE * 2; i++ )
        System.out.println( "Found " + i + " at " +
                                 binarySearch( a, new Integer( i ) ) );
    }
}

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

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