CODEWITHSUNDEEP
carraysinfinite-loopbinary-search
Zahra Mahmood
Zahra Mahmood

Reputation: 35

Why is this binary search giving me an infinite loop?

I am trying to do a binary search. I really can't think of why I am getting an infinite loop? Is is because I ignored the null value somewhere? The value, values[], and n are being provided by a different file, and they are written by someone else, and are, for the purposes of this question, perfectly coded. 

bool search(int value, int values[], int n)
{
    int upper_bound = n - 1;
    int lower_bound = 0;
    int middle = (upper_bound + lower_bound) / 2; 

    while (lower_bound <= upper_bound)
    {
        if (values[middle] == value)
        {
            return true;
        }
        else if (values[middle] > value)
        {
            upper_bound = middle - 1; 
        }
        else if (values[middle] < value)
        {
            lower_bound = middle + 1;
        }
        else 
        {
            return false;
        }

    }
    return false;
}

Thank you all so much.

Upvotes: 0

Views: 859

Answers (2)

Anil
Anil

Reputation: 1788

the middle value is fixed. It is not changing as the values of upper_bound and lower_bound are changing.

Upvotes: 0

Debojit Saikia
Debojit Saikia

Reputation: 10632

You need to calculate the value of middle inside the while loop:

while (lower_bound <= upper_bound){
int middle = (upper_bound + lower_bound) / 2;
...
}

As the value of middle should change every time you are changing the value of either lower_bound or upper_bound.

Upvotes: 1

Related Questions