Stuck in a while loop in cs50 pset3 binary search

Question

I am trying to implement a binary search using a while loop. It seems to work when the int I am looking for is in the array; however, when the int I am searching for is not there, the program seems to get stuck in the loop, without returning false. I have been using the gdb, but I still can't seem to figure out the bug. As you can see, I have maybe added a bunch of extra if statements, etc. trying to figure this out.

bool search(int value, int values[], int n) {
    sort(values, n);

    int begin = 0;
    int end = (n - 1);

    if (n < 1) {
        return false;
    }
    while (end > begin + 1) {
        int center = ((begin + end) / 2);
        if (values[0] == value) {
            return true;
        }
        if (begin == value) {
            return true;
        }
        if (end == value) {
            return true;
        }
        if (end == (begin + 1) || end == begin) {
            if (end == value || begin == value) {
                return true;
            } else {
                return false;
            }
        }
        if ((values[center]) == value) {
            return true;
        } else
        if ((values[center]) > value) {
            end = center;
        } else
        if ((values[center]) < value) {
            begin = center;
        } else {
            return false;
        }
    }
    // TODO: implement a searching algorithm
    return false;
}

`begin` and `end` are indexes, why are you comparing them with `value`? — Barmar, Nov 23 '16 at 20:32
There are lots of binary search algorithms available here on SO (there are bound to be, and a fair number of them will be related to CS50, too). You should look at some of those to see that your code is vastly over-complicated as well as incorrect. For instance, there is useful code in [First and last occurrence for binary search in C](http://stackoverflow.com/questions/35147784/), which deals with some more complex cases than you need, but also contains the code you need. You could look at [if statement not recognizing true conditions](http://stackoverflow.com/questions/38468878/) too. — Jonathan Leffler, Nov 24 '16 at 05:43
@aknys: you can accept one of the answers by clicking on the grey checkmark below its score. — chqrlie, Dec 12 '16 at 02:40

score 0 · Answer 1 · answered Nov 24 '16 at 04:15

Why you are doing this?

if (values[0]==value)
    {
        return true;
    }
    if (begin == value)
    {
        return true;
    }
    if (end == value)
    {
        return true;
    }
    if (end == (begin+1) || end == begin)
    {
        if (end == value || begin == value)
        {
        return true;
        } 
        else
        {
        return false;
        }
    }

They are not necessary. You can do just like below

while(end>beg+1 && values[center]!=value)
     {
     if ((values[center])>value)
        end = center-1;
    else if (values[center]<value)
        begin = center+1;
    center=(end+begin)/2;
     }
     if(values[center]==value)
           return true;
     else return false;
    }

And i don't understand why you used sort(values,n); If it is a C++ code then use it as sort(values,values+n); and if it is a C code then sort the array using any algorithm according to your array size and time. Thank you.

score 0 · Answer 2 · answered Nov 27 '16 at 23:51

You are unnecessarily overcomplicating this simple thing. You can just remove all the extra stuff in your code and use this

   `if ((values[center])==value)
    {
        return true;
    }
    else if ((values[center])>value)
    {
        end = center-1;
    }
    else if ((values[center])<value)
    {
        begin = center+1;
    }

`

chqrlie · Answer 3 · 2016-11-28T00:07:02.210

Your code is too complicated. Here are some hints:

You should use a range with the left index included and the right index excluded, this is idiomatic in C and leads to simpler algorithms.
You should compute center = start + (end - start) / 2; instead of center = (start + end) / 2; to avoid the potential integer overflow if start and end are very large.
The array size should have type size_t, potentially larger than int.
compare the value with that of the element at the middle of the range:
- if equal, the value was found, return true.
- if smaller, reduce the range to the left part, center excluded.
- otherwise reduce the range to the right part, center excluded.
if the range is empty, the value was not found, return false.

Here is a simpler version:

bool search(int value, int values[], size_t n) {
    // Assuming values is sorted before calling this function
    //sort(values, n);

    size_t begin = 0;
    size_t end = n;

    while (begin < end) {
        size_t center = begin + (end - begin) / 2;
        if (value == values[center]) {
            return true;
        }
        if (value < values[center]) {
            end = center;
        } else {
            begin = center + 1;
        }
    }
    return false;
}

Stuck in a while loop in cs50 pset3 binary search

3 Answers3