Binary Search Runs Blank (Code Review)

[Pegasus1]

I am trying to make a program that implements a boolean binary search function (without using the algorithms found in the Standard C++ Library) that is tested by assert statements. However, I do not know why the following runs as a blank. I would appreciate any help.

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

bool binarySearch(int a[], int size, int k);

int main()
{
    int a[] = {1,2,3,4,5};
    assert(binarySearch(a,5,5)== true);

    int b[] = {-9,-4,0,2,4,12,99};
    assert(binarySearch(b,7,5)== false);

    int c[] = {0,10,12,14,20};
    assert(binarySearch(c,5,5)== false);


    cout << "All tests have successfully passed." << endl;
}

bool binarySearch(int a[], int size, int k)
{
    int s = 0;
    int e = size - 1;
    int m = (s + e)/2;
    
    while(s <=e)
    {
        if(k == a[m])
        {
            return true;  
        }
        else if(k < a[m])
        {
            e = m - 1; 
        }
        else if(k > a[m])
        {
            s = m + 1;
        }
    }
    return false;
}

[MatthewRock]

What do you mean by "runs blank"?
Anyway, m is never updated in the loop, and you check for a[m], so you always check the same value.

[Pegasus1]

I mean nothing happens when I run the output file. It should print "All tests have successfully passed," but it doesn't. It runs but doesn't print anything.

[MatthewRock]

Because of infinite loop - you're setting either e to m-1 or s to m+1, but m is constant in your code. You forgot to update m.

PS. By the way, these are terrible variable names.

[Pegasus1]

Thanks!

Do you recommend I write out 'start', 'midpoint', and 'end' instead of using 's', 'm', and 'e'?

I revised the original code by adding lines 38 and 43 in the following code. It works now!

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

bool binarySearch(int a[], int size, int k);

int main()
{
    int a[] = {1,2,3,4,5};
    assert(binarySearch(a,5,5)== true);

    int b[] = {-9,-4,0,2,4,12,99};
    assert(binarySearch(b,7,5)== false);

    int c[] = {0,10,12,14,20};
    assert(binarySearch(c,5,5)== false);


    cout << "All tests have successfully passed." << endl;
}

bool binarySearch(int a[], int size, int k)
{
    int s = 0;
    int e = size - 1;
    int m = (s + e)/2;

    while(s <=e)
    {
        if(k == a[m])
        {
            return true;
        }
        else if(k < a[m])
        {
            e = m - 1;
            m = (s + e)/2;
        }
        else if(k > a[m])
        {
            s = m + 1;
            m = (s + e)/2;
        }
    }
    return false;
}

[MatthewRock]

Yes. Generally, when writing variable names try to make them as clear as possible(but don't make them too long as well). start, midpoint and end make it obvious what we're referring to, when s e and m can be a problem, while StartingPointOfBinarySearchAlgorithm and similar java boilerplate would be just a waste of keystrokes.

Anyway, glad to help. Two more minor improvements I'd do:

1) the three if checks are mutually exclusive - so you can drop "if" in the last else - there's no way that after failing the first two tests we get anything other than k > a[m].
2)You entered the same definition for m three times. This copy-and-paste indicates that something is wrong. I'd either move the m = (s + e) / 2 to the end of the while loop, or to the beginning(this way you can remove this from the line 27 too), e.g.:

    while(s <=e)
    {
        int m = (s + e)/2;
        if(k == a[m])
        {
            return true;
        }
        else if(k < a[m])
        {
            e = m - 1;
        }
        else
        {
            s = m + 1;
        }
    }

[Pegasus1]

Thanks for the helpful feedback!

I had a feeling that I had some superfluous lines.

Is it considered "best practice" in the field to write out variables like 'start', 'midpoint', and 'end' in the operative code, or to just use variables like 's', 'm', and 'e' and add comments, or is it just a matter of preference?

I optimized the code to read as follows:

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

bool binarySearch(int a[], int size, int k);

int main()
{
    int a[] = {1,2,3,4,5};
    assert(binarySearch(a,5,5)== true);

    int b[] = {-9,-4,0,2,4,12,99};
    assert(binarySearch(b,7,5)== false);

    int c[] = {0,10,12,14,20};
    assert(binarySearch(c,5,5)== false);

    int d[] = {-1000,10,99,100,1000};
    assert(binarySearch(d,5,99)== true);

    cout << "All tests have successfully passed." << endl;
}

bool binarySearch(int a[], int size, int k)
{
    int s = 0;              // 's' stands for the starting point of the binary search algorithm.
    int e = size - 1;       // 'e' stands for the ending point of the binary search algorithm.

    while(s <=e)
    {
        int m = (s + e)/2;  // 'm' stands for the midpoint of the binary search algorithm.

        if(k == a[m])
        {
            return true;
        }
        else if(k < a[m])
        {
            e = m - 1;
        }
        else 
        {
            s = m + 1;
        }
    }
    return false;
}

[MatthewRock]

The 'field' has many best practices(some mutually exclusive), but what I(and I guess that many programmers would agree with me) think is the best is to use common sense and readable names instead of comments.

When you use name "size", you need to type additional 3 characters each time you refer to it, but that's not much at all, and makes code readable - you instantly see where the value is used, and what's its purpose.

When you use name "s" and comments, when I see "s" for the first time I have to look for the comment(or try to guess myself). I also have to read the comment each time I don't look at the code for a long time. I can also miss the comment. Comments aren't good for this purpose.

When you use name "s" without any additional info, I can only guess what it means. Maybe I will find out eventually(I did so in here), but that's just additional intellectual overhead - and if your program doesn't work as intended, even more of overhead.

On the other hand, use common sense. When you do some for(int i = 0; i < ....), i is standard name for this type of variable and no one will complain, but other names should be self-explanatory.

Generally, comments should be used to note something or explain why are we doing something(explain harder/stranger bits of algorithm), not describe what code means.

[Pegasus1]

That was very helpful--thank you!