c - Binary Search Recursion Algorithm Issue In C

Question

Ok, so I'm given the function

int bin(int value, int size, int array[])

I am supposed to find "value" within "array[]", but the issue at hand here is that in most cases, we have something along the lines of

int bin(int value, int max, int min, int array[])

The recursion, logically, is a lot easier on this part due to the fact I can still pass the number I am at, as well as remember the size of the array.

int bin(int array[], int value, int min, int max)
{
    if(max < min)
        return -1;
    else
    {
        int mid = min + (max - min)/2;

        if(array[mid] > value)
            return bin(array, value, min, mid-1);
        else if(array[mid] < value)
            return bin(array, value, mid+1, max);
        else
            return mid;
    }

But since I can only pass 1 integer, how exactly would I adjust this algorithm for it? In essence, I would only be able to do something like this, but I KNOW it will not logically work. Is there a way, though, that I can see the size of the array? I tried it, but the numbers weren't crunching right.

   int bin(int array[], int value, int size)
    {
            int mid = size/2;

            if(array[mid] > value)
                return bin(array, value, size-(size/2));
            else if(array[mid] < value)
                return bin(array, value, size+(size/2));
            else
                return mid;
    }

score 13 · Accepted Answer

ベースも明示的に渡す必要があります。

int
bin(int array[], int value, int size)
{
        int mid = size/2;

        if(array[mid] > value)
            return bin(array, value, size/2);
        else if(array[mid] < value)
            return bin(&array[mid], value, size/2);
        else
            return mid;
}

「if(array[mid] < value)」の場合の「&array[mid]」に注意してください

毎回、ベース + オフセット副最小/最大インデックスを使用して、配列の正しい半分を検索します

score 0 · Accepted Answer

異なる引数セットを持つメソッドを持つ目的は、ユーザーがメソッドを簡単に呼び出せるようにすることです。これは再帰では非常に一般的です。

int bin(int value, int size, int array[])署名を持つユーザーが使用できるパブリックメソッドがあります。

int bin(int value, int max, int min, int array[])次に、署名付きのプライベートな内部ヘルパーメソッドが存在する必要があります。

ポイントは、このメソッドを呼び出す人は、開始インデックスと終了インデックスではなく、配列のサイズを渡したいということです (彼らにとって、開始インデックスは常に 0 であり、終了は常にサイズ-1 である必要があるため)。そのように事前設定された引数を持つメソッドを持つことは悪い習慣です。

開始値と終了値 (最小値と最大値) を持つヘルパーメソッドは、より効率的な計算のために再帰呼び出しで使用され、不要な引数をユーザーから隠します。

メソッドは次のようになります。

int bin(int value, int size, int array[]) {
    return bin(value, size - 1, 0, array);
}

score 0 · Accepted Answer

int * binSearch (int *arr,int size, int num2Search)

{

    if(size==1)

        return ((*arr==num2Search)?(arr):(NULL));

    if(*(arr+(size/2))<num2Search)

        return binSearch(arr+(size/2)+1,(size/2),num2Search);

    if(*(arr+(size/2))==num2Search)

        return (arr+(size/2));

    return binSearch(arr,(size/2),num2Search);

}

私の関数では、同じパラメーターを取得し、値のアドレスを返します。

c - Binary Search Recursion Algorithm Issue In C

3 に答える 3

Related

Reference