binary search wont print the right answer

[helloworld1234]

Hello everyone,

I have written a code for binary search for my class. My professor asked us to create it using bool, and the header function "bool binarySearch(int a[], int start, int end, int number)".

I am having some issues with it. it all seems fine until i get to part where i have to print the answer in my main function. I am not sure what's wrong. can you please help me? i'd really appreciate it

#include <iostream>

using namespace std;

bool binarySearch(int a[], int start, int end, int number)
{
    int mid;
    bool b=false;


    if(start<=end)
    {
        b=true;
    }

    while (B)/>/>
    {   
        b=false;
        mid= (start+end)/2;

        if (number == a[mid])  //if whatever is in index 3 is equal to the number entered
            return mid;

        else if (number>a[mid]) 
        {   start=mid+1;
                b=true;
        }
        else
        {   end= mid-1;
            b=true;
        }
    }

}
int main()
{
    int a[]={5,10,23,34,45,55,66,78,81,98}; 
    int number;
    int answer;

    cout<< "Enter a number: "<<endl;
    cin>> number;


    answer= binarySearch(a,0,9,number);

    cout<< "you entered "<<number<<" located at index: "<< answer;

system("pause");
return 0;

}

[JasonHippy]

Took me a little while to understand what you were doing in your code there, it initially looked as if you'd forgotten to return a value from your binarysearch function.

But then I saw in the middle of the binarysearch functions code that you were returning the int value mid. But the function is supposed to return a bool meaning it can only return true or false. So at the point of returning, if mid is equal to 0 the function will return false (or 0). For any other value of mid it will return true (or 1).
Which probably explains your problem.

Changing the signature of the function to return an int would solve this problem, but that isn't what your professor has asked for. He wants you to use a function that returns bool and it can only be assumed that the bool return is intended to signify whether the binary search function failed or succeeded in its attempt to find the user entered value in the passed in array. A bool return value cannot signify the index position of the number in the array. To output the array position you'd need to either:
A: Output the array position directly from inside the binarysearch function when a match is found.
B: Add an additional parameter to your function (a pointer or reference to an int), which would act as an output parameter, then inside your binarysearch function you set the output parameter to the index of the found number.

But again, option B would mean changing the signature of the function to add an extra parameter. Which is not what your professor wants. So that would be out of the question, which leaves you with one course of action. Option A.

In which case you need to do the following:
Inside binarysearch():
If/when the target number is found, use cout to output the index/location of the number and then return true.
e.g.

std::cout << "The number " << number << " was found at index " << mid << "\n";
return true;

If the number is not found in the array, your function should return false.

Then in your main function you can simply check the return value of the function and output a message if the number is NOT found. e.g.

if(!binarySearch(a,0,9,number))
    std::cout << "The number you entered (" << number << ") was not found in the array!\n";

That's the simplest way around the problem that I can see!

BTW: I'm assuming that line 16: while (B)/>/> is supposed to be while (b)

[Gonbe]

You're returning a bool, which can only be true or false. I'm not sure what your teacher wants, but it seems to me you only have to check whether or not a specified number is part of the array. (Or print the index from the function, but that seems like poor design) So something like this:

#include <iostream>

using namespace std;

bool BinarySearch(const int a[], const int start, const int end, const int number)
{
    if      (start >  end) return false;

    int middle = start + ((end - start) / 2);

    if      (a[middle] > number) return BinarySearch(a, start     , middle - 1, number);
    else if (a[middle] < number) return BinarySearch(a, middle + 1, end       , number);
    else                         return true;
}


int main()
{
    int a[] = {5, 10, 23, 34, 45, 55, 66, 78, 81, 98};
    int number(0);

    cout << "Enter a number: " << endl;
    cin >> number;

    if (BinarySearch(a, 0, 9,number))
        cout << "The array does contain the number " << number << endl;
    else
        cout << "The array does not contain the number " << number << endl;

    return 0;
}

[JasonHippy]

Gonbe's solution above would be a more logical solution to the problem and would be how I would expect a bool function like this to be used. But again, if it has been specified by your professor that the index of the number should be output by the program, you should use my solution. (I was only going by the information supplied by the OP and went with the assumption that they had to output the index of the number when it was found, otherwise I would have suggested exactly what Gonbe has!)

But if your professor has not specified that you should output the array position of the number when it is found, then Gonbe's answer is bang on the money!

[helloworld1234]

thanks a lot, your response helped me figure out the right answer!

[bguild]

The natural way to meet the requirements of the project is option C: create two separate search functions; one that has the required signature and returns true or false for success or failure, and another search function that returns the index.

[helloworld1234]

okay now im having another problem....whenever the number is found, it prints the response twice..

#include <iostream>
using namespace std;



bool binarySearch(int a[], int start, int end, int number)
{
    int mid;
    bool b=false;

    if(start<=end)  
    {
        b=true;
    }

    while (b)
    {   
        b=false;
        mid= (start+end)/2;

        if (number == a[mid])  
        {
            cout<< "The number you entered "<< number<< " is located in index "<<mid;
            break;
        }
        else if(start==end)
        {       
            return false;
        }
        else if (number>a[mid]) 
        {   
            start=mid+1;
                b=true;
        }
        else
        {   end= mid-1;
            b=true;
        }
    }

}
int main()
{
    int a[]={5,10,23,34,45,55,66,78,81,98}; 
    int number;
    int answer;

    cout<< "Enter a number: "<<endl;
    cin>> number;

    answer= binarySearch(a,0,9,number);

    if(!binarySearch(a,0,9,number))
    cout << "Your number " << number << " was not found in the array"<<endl;

cout<<endl;
system("pause");
return 0;    
}

is it possible to do

else { cout << "your number" <<number<< "is located in index"<< a[answer];

in the main function right after the if statement

[bguild]

whenever the number is found, it prints the response twice..

You have clearly shown why it is a bad idea to use cout to deliver the results of a search function. I highly recommend that you change your tactic and get the result some other way.

[helloworld1234]

just noticed all the responses from everyone else. i forgot to refresh. i will read them all and see how i can fix the problems i am having. thanks to everyone who has responded. i really appreciate it

[helloworld1234]

In response to Gonbe's code, if i changed

bool BinarySearch(const int a[], const int start, const int end, const int number)
to

bool BinarySearch( int a[], int start, int end, int number)

and kept the rest of the code, would it have the same outcome?

i know what const is used for but i am trying to understand why it's better to use const than just int alone.

thanks again

[Gonbe]

It's a "habit" of mine. It's good practice to make things that should remain constant const for various reasons. You may omit it if it makes you more confident. You might also wonder why the middle is calculated in such a weird way. It's also something you may change back. It's something to prevent arithmetic overflow but it's not really required for this example I guess.

The reason I had rewrittne the function in the first place is because the function you created has some oddities in it which I think relate to one of your later questions. In my opinion you should think about it carefully and re-write it because in its current form its a bit of a mess. Generally I feel that I can get the point across easiest by commenting code line by line, I hope it convinces in this case too..

bool binarySearch(int a[], int start, int end, int number)
{
    int mid;        // Variable which will hold the index for the middle element.
    bool b=false;   // A flag indicating whether or not we should stop. (Name your variables better)

    // The index "start" has to be smaller or equal to "end", otherwise we're do not have to do anything (anymore).
    if(start<=end)
    {
        b=true;
    }

    // As long as the "keep-going" flag is true..
    while (b)
    {
        // Set the flag to false, unless proven otherwise in the remains of this iteration.
        // Note that this flag is useless right now as all options that would have not set it
        // to true either return from the function or break out of the loop themselves. Re-design your function..
        b=false;

        // Calculate the index of the middle element.
        mid= (start+end)/2;

        // We have found our number in the middle of the search range
        if (number == a[mid])
        {
            // Print some text and break out of the while loop.
            cout<< "The number you entered "<< number<< " is located in index "<<mid;
            break;
        }
        // If our search range is only 1 element big and it wasn't found in the previous if statement -> it's not present. (return false)
        else if(start==end)
        {
            return false;
        }

        // Our search range is bigger than 1 element. If the number we're at is smaller than our desired number it means we should look at the section after it.
        else if (number>a[mid])
        {
            // The next iteration should search "mid + 1 till end".
            start=mid+1;

            // Set our "keep-going" flag.
            b=true;
        }
        else
        {
            // The next iteration should search "start till mid - 1".
            end= mid-1;

            // Set our "keep-going" flag.
            b=true;
        }

        // Another error here is that "start" could become bigger than "end" in this loop. For example, say start = 0, end = 1, a = {2,3} and number = 1. Then mid = 0. This 
        // loop will then set "end" to -1 and continue. Meaning the new range will be 0 - -1 and the loop will continue with those values. This is undesired.
    }

    // Oops, the function states it returns a bool but nothing is returned here. 
    // You get here from multiple types of cases. As mentioned you should redesign your function before continuing.
}

[helloworld1234]

#include <iostream>
using namespace std;



bool binarySearch(int a[], int start, int end, int number)
{
    int mid;
    bool b=false;

    if(start<=end)  
    {
        b=true;
    }

    while (b)
    {   
        b=false;
        mid= (start+end)/2;

        if (number == a[mid])  
        {
            cout<< "The number you entered is located in index " <<mid; 
            break;
        }
        else if(start>end)
        {
            return false;
        }
        else if (number>a[mid]) 
        {   
            start=mid+1;
                b=true;
        }
        else
        {   end= mid-1;
            b=true;
        }
    }


}
int main()
{
    int a[]={5,10,23,34,45,55,66,78,81,98}; 
    int number;
    int answer;

    cout<< "Enter a number: "<<endl;
    cin>> number;

    answer= binarySearch(a,0,9,number);

    if(!binarySearch(a,0,9,number))
    cout << "Your number " << number << " was not found in the array"<<endl;

cout<<endl;
system("pause");
return 0;    
}

that is my current code. It seems to be working fine except that it keeps printing "your number is in index" twice...i don't understand why.

if there is no way to remedy that, then i will go with gonbe's approach since it also works (minus the indication of which index)

[Gonbe]

I guess you have 3 options:
a) You return a bool and print the index from within the function.
b) You return a bool and return the index using a call-by-reference parameter.
c) You return the index if found, and otherwise -1. (Or whatever value that can't normally be returned)

I'd probably go for c normally. Here's a quick example of b:

#include <iostream>

using namespace std;

bool BinarySearch(const int a[], const int start, const int end, const int number, int& index)
{
    if (start >  end) return false;

    index = start + ((end - start) / 2);

    if      (a[index] > number) return BinarySearch(a, start    , index - 1, number, index);
    else if (a[index] < number) return BinarySearch(a, index + 1, end      , number, index);
    else                         return true;
}

int main()
{
    int a[] = {5, 10, 23, 34, 45, 55, 66, 78, 81, 98};
    int number(0), index(0);

    cout << "Enter a number: " << endl;
    cin >> number;

    if (BinarySearch(a, 0, 9, number, index))
        cout << "The array contains the number " << number << " at index " << index << ".\n";
    else
        cout << "The array does not contain the number " << number << ".\n";

    return 0;
}

[Gonbe]

that is my current code. It seems to be working fine except that it keeps printing "your number is in index" twice...i don't understand why.

You're printing within your function and you are calling your function twice. Also you're assigning a boolean value to an integer (answer) which you're not even using.

-edit-
Minor cleanup of your function. More could be done, but atleast it's more readable now. I only did the things started in the summation at the top of the function; the rest is unaltered..

#include <iostream>
using namespace std;

bool binarySearch(int a[], int start, int end, int number)
{
    // 1. Removed the boolean 'b' as it was useless. (Validness of the range is now the condition for the loop)
    // 2. Instead of breaking out of the loop when the value is found, true is returned directly.
    // 3. Removed the start > end check inside the loop as it's redundant with the loop condition itself.
    // 4. Added a return false statement at the end of the function.
    int mid;

    while (start <= end)
    {
        mid= (start + end)/2;

        if (number == a[mid])
        {
            cout<< "The number you entered is located in index " << mid << ".\n";
            return true;
        }
        else if (number>a[mid])
        {
            start=mid+1;
        }
        else
        {
            end= mid-1;
        }
    }

    return false;
}

int main()
{
    // 1. Removed "answer" and anything associated.

    int a[]={5,10,23,34,45,55,66,78,81,98};
    int number;

    cout<< "Enter a number: "<<endl;
    cin>> number;

    if(!binarySearch(a,0,9,number))
        cout << "Your number " << number << " was not found in the array.\n";

    return 0;
}

[helloworld1234]

YES!! thanks so much, i also realized the answer function was not even being used. taking it out fixed the problem.

it works fine now without it. but just a question about the code overall. I am a beginner so im sure it's not the best way to code it. but in your opinion is it extremely inefficient, and that the way you've done it is better?

or does it really not matter since it gets the job done?

[helloworld1234]

thanks a lot, Gonbe.

I understand the changes you made. i originally decided to declare bool b and all that stuff in the beginning because in class, my professor used bool=true, and then bool=false after the while loop when demonstrating bubble sort and selection sort.

i like it better without having to use all that stuff in the beginning. thanks again to all of you

[Gonbe]

but in your opinion is it extremely inefficient,

That wasn't what I was saying. Your early versions contained things that resulted in behaviour that couldn't possibly be desired. In addition it contained things that served no purpose. (like the 'b' variable) I've edited my previous post to show how you can remove some stuff without really changing what the function does. I do think these are things you should try to look out for especially.

In this case you had to implement a specific type of searching algorithm meaning there's only so much you can do here performance-wise. (It'd be different if you had to develop any searching algorithm)

or does it really not matter since it gets the job done?

As a student I'd just go for something that "gets the job done" unless you've been given explicit performance requirements. But as a mentioned earlier, something that gets the job done should still be "proper"; it's no excuse for sloppy code. It is allowed to be less complicated at the cost of efficiency though. If I were you I'd focus on readable programs and at some point you could think about performance once you've got the hang of simple things.

e.g: Sorting alghorithms is something that is lectured at most institutions. If you need to sort something as part of a bigger assignment I'd go for something easy, like bubblesort for example. You'll one day find out it's quite horrible performance wise but as a beginner it's relatively easy to implement and easy to reason about which allows you to focus on the task itself. If you'd worry to much about performance and end up trying to implement something more complicated like for instance quicksort or merge sort you're overcomplicating things and you are likely missing the point of the assignment.

[helloworld1234]

okay thank you