CODEWITHSUNDEEP
c#algorithmbinary-search
Gilad
Gilad

Reputation: 6595

Binary Search C# implementation

Here is one implementation I did for Binary search

public int FindIndexRecursive(int numberToFind, int[] array, int indexMin, int indexMax)
{
    if (indexMin > indexMax)
    {
        return -1;
    }

    int mid = ((indexMax - indexMin) / 2 ) + indexMin;

    if (array[mid] < numberToFind)
    {                
        return FindIndexRecursive(numberToFind, array, mid, indexMax); 
    }
    else if (numberToFind < array[mid])
    {
        return FindIndexRecursive(numberToFind, array, indexMin, mid);
    }
    else 
    {
        return mid;
    }
}

it works fine. I asked a question https://codereview.stackexchange.com/questions/71815/binary-search-using-recursion-iteration-shifted-array

and I was answer that I can change my mid calculation

from: int mid = ((indexMax - indexMin) / 2 ) + indexMin;
to: int mid = ((indexMax - indexMin) / 2 );

public int FindIndexRecursive2(int numberToFind, int[] array, int indexMin, int indexMax)
{
    if (indexMin > indexMax)
    {
        return -1;
    }

    int mid = ((indexMax - indexMin) / 2);
    //since the array is sorted
    if (numberToFind < array[mid])
    {
        return FindIndexRecursive2(numberToFind, array, indexMin, mid-1);
    }
    else if (numberToFind > array[mid])
    {
        return FindIndexRecursive2(numberToFind, array, mid+1, indexMax);
    }
    else
    {
        return mid;
    }
}

However now I get a stack overflow, what am I missing in my new implementation?

Upvotes: 1

Views: 2954

Answers (3)

shekhar
shekhar

Reputation: 1432

You might have been advised that, to reduce the number of operations to compute the mid.

(indexMax - indexMin)/2 + indexMin equals (indexMax + indexMin)/2

Upvotes: 3

Palec
Palec

Reputation: 13577

The original int mid = ((indexMax - indexMin) / 2 ) + indexMin; computes the distance beween indexMax and indexMin halves it and uses it to index the original array relatively to indexMin.

The new int mid = ((indexMax - indexMin) / 2 ); is wrong and should contain a + instead of the -: int mid = ((indexMax + indexMin) / 2 ); This uses the fact that mean of two values is just in the middle between them.

If you take a pen and write this and the original expression as expressions with fractions, you’ll come to the conclusion that they are equal:

indexMax - indexMin              indexMax - indexMin   2 · indexMin   indexMax + indexMin
------------------- + indexMin = ------------------- + ------------ = -------------------
         2                                2                  2                 2

Upvotes: 4

Erti-Chris Eelmaa
Erti-Chris Eelmaa

Reputation: 26318

The way you take middle, is (low+high)/2. Otherwise you'll get stack overflow exception.

Upvotes: 3

Related Questions