首页 文章

二进制搜索的递归函数

提问于
浏览 次
-7

为二分查找创建递归函数 .
此函数接受已排序的数组和要搜索的项，并返回项的索引（如果项在数组中），或返回-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;
}
c++ recursion binary-search

3 回答

  • 7

    在美国有一个孩子的游戏，其中一个孩子选择1到10之间的数字，另一个孩子必须猜测这个数字 . 如果他们猜错了，第一个孩子会说“更高”或“更低” .

    大多数孩子开始随机猜测，平均需要4-5次尝试才能成功 . 我意识到（这可能就是我最终进入计算机科学的原因），最好的办法是选择中点（5.5，所以选择5或6.我会选择5） . 根据他们的说法（“更高”或“更低”），选择新的范围，1-4或6-10 . 选择该范围中间的数字（2或8） . 继续将范围分成两半，直到得到数字 .

    这是对已排序数组的二进制搜索（排序数组为1到10之间的数字） .

    要在代码中实现它，只需继续执行上述相同的过程 . 选择范围的中点，并根据答案创建新范围 .

    这是one solution in Java，它会反复这样做：

    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 ) ) );
    }
}
    回复于
  • 3

    你也可以google "recursive binary search"和voila！

    EDIT- 维基百科知道所有（特别是涉及到cs）：

    [二进制搜索算法]最直接的实现是递归的，它递归搜索比较所指示的子范围：

    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
   }
    回复于
  • -1

    只需使用std::binary_search . 告诉导师该函数实际上是在your_favorite_compiler中递归实现的 .

    回复于

相关问题