Binary Search C# implementation

Question

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?

Did you mean to write: int mid = (indexMax + indexMin) / 2 ? — Michael Petito
– Michael Petito, Commented Dec 20, 2014 at 17:12
Check out this answer for the simplest implementation of recursive Binary Search using C# 12. — Ash K
– Ash K, Commented Jan 28, 2024 at 21:14

Palec · Accepted Answer · 2014-12-20 17:18:59Z

4

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

answered Dec 20, 2014 at 17:18

Palec

13.8k8 gold badges80 silver badges145 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

shekhar · Accepted Answer · 2017-04-04 16:39:06Z

3

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

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

edited Apr 4, 2017 at 16:39

answered Dec 20, 2014 at 17:38

shekhar

1,4622 gold badges17 silver badges27 bronze badges

1 Comment

Erti-Chris Eelmaa Over a year ago

@neo; they are by no means equal :P, different formulas, different behaviors.

Erti-Chris Eelmaa · Accepted Answer · 2014-12-20 17:13:15Z

3

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

answered Dec 20, 2014 at 17:13

Erti-Chris Eelmaa

26.6k6 gold badges65 silver badges83 bronze badges

Collectives™ on Stack Overflow

Binary Search C# implementation

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related