How do I implement binary search for an array of integers?

Question

I want to implement binary search for an array of integers. I made sure that array sorted incrementally. But my function is not tracking all the cases and some of the checks fail. What am I missing here? Value stands for integer I'm trying to find.

bool search(int value, int array[], int n)
{   
    int left = 0;
    int right = n - 1;
    int middle = (left + right) / 2;

while (right >= left)
{
    if (array[middle] == value)
    return true;
    else if (array[middle] < value)
    right = middle;
    else if (array[middle] > value)
    left = middle + 1;

    middle = (left + right) / 2;
}

return false;
}

My guess is that some left or right border cases are not predicted. I also not strong about while condition.

Debugger of use printf - debugging. Output of left, middle, right for a failing example should lead to the problem. — MrSmith42
– MrSmith42, Commented Jan 27, 2017 at 15:44
How do you implement binary search? Carefully. It's been observed that the first implementation of binary search was published in 1946, but the first correct implementation of binary search was published in 1960. You'll learn a lot by debugging your own version, and making sure it works on all cases. — Steve Summit
– Steve Summit, Commented Jan 27, 2017 at 15:46
@SteveSummit Good point. I believe the typical pitfall is integer overflow in the middle computation, which is easily missed in human-scaled test cases. Wikipedia has notes on this. The recommended expression is middle = left + (right - left) / 2;. — unwind
– unwind, Commented Jan 27, 2017 at 15:50

Pylyp Lebediev · Accepted Answer · 2017-01-27 21:01:59Z

6

You mixed left and right, if array[middle] < value you have to change left.

bool search(int value, int array[], int n)
{
    int left = 0;
    int right = n - 1;
    int middle = left + (right - left) / 2;

    while (right >= left)
    {
        if (array[middle] == value)
            return true;
        else if (array[middle] > value)
            right = middle - 1;
        else if (array[middle] < value)
            left = middle + 1;

        middle = (left + right) / 2;
    }
    return false;
}

will work: http://ideone.com/VSAhnZ

Further improvements can be:

You can exclude middle in the else parts, because you have already proved that it is not the correct value (right = middle; => right = middle - 1;)
The second else if can be replaced by an else. If it is not the value and not smaller you do not have to test if it is larger.

edited Jan 27, 2017 at 21:01

Pylyp Lebediev

2,1515 gold badges32 silver badges50 bronze badges

answered Jan 27, 2017 at 15:48

mch

9,8243 gold badges33 silver badges46 bronze badges

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

1 Comment

Vladislav Kovechenkov Over a year ago

Got it. Your answer helped me a lot, big thanks. Can't believe I couldn't figure out this kind of mixing for such a long time. I'll try to be more attentive in the future.

rx6147 · Accepted Answer · 2017-01-27 15:54:38Z

-1

Standard binary search algorithm can be found anywhere. but just correcting your code:

bool search(int value, int array[], int n)
{   
    int left = 0;
    int right = n - 1;
    int middle;
    while (left <= right)
    {
         middle = (left + right) / 2;    
        if (value > array[middle] )
            left = middle + 1;
        else if (value < array[middle])
            right = middle - 1;                
        else 
            return true;
     }
     return false;
}

edited Jan 27, 2017 at 15:54

answered Jan 27, 2017 at 15:48

rx6147

192 bronze badges

Collectives™ on Stack Overflow

How do I implement binary search for an array of integers?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related