一千萬個為什麽

搜索

二進制搜索的遞歸函數

為二進制搜索創建遞歸函數。
此函數接受已排序的數組和要搜索的項,並返回項的索引(如果項在數組中),或返回-1(如果項不在數組中)。
此外,編寫測試程序來測試您的功能。

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;
}

最佳答案

在美國有一個孩子的遊戲,其中一個孩子選擇1到10之間的數字,另一個孩子必須猜測這個數字。如果他們猜錯了,第一個孩子會說“更高”或“更低”。

大多數孩子開始隨機猜測,平均需要4-5次嘗試才能成功。我意識到(這可能就是我最終進入計算機科學的原因),最好的辦法是選擇中點(5.5,所以選擇5或6.我會選擇5)。根據他們的說法(“更高”或“更低”),選擇新的範圍,1-4或6-10。選擇該範圍中間的數字(2或8)。繼續將範圍分成兩半,直到得到數字。

這是對已排序數組的二進制搜索(排序數組為1到10之間的數字)。

要在代碼中實現它,只需繼續執行上述相同的過程。選擇範圍的中點,並根據答案創建新範圍。

這是一個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 ) ) );
    }
}

轉載註明原文: 二進制搜索的遞歸函數