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
– Barmar, Commented Nov 23, 2016 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, 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 too. — Jonathan Leffler
– Jonathan Leffler, Commented Nov 24, 2016 at 5:43
@aknys: you can accept one of the answers by clicking on the grey checkmark below its score. — chqrlie
– chqrlie, Commented Dec 12, 2016 at 2:40

user6794537 · Accepted Answer · 2016-11-24 04:15:12Z

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.

Sanjay-sopho · Accepted Answer · 2016-11-27 23:51:05Z

0

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;
    }

`

answered Nov 27, 2016 at 23:51

Sanjay-sopho

4293 silver badges15 bronze badges

Comments

chqrlie · Accepted Answer · 2016-11-28 00:07:02Z

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;
}

Collectives™ on Stack Overflow

Stuck in a while loop in cs50 pset3 binary search

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related