Beans
Beans

Reputation: 139

Binary Search Function- Output the number of compares even the number cannot be found in the array

The code below is used to perform binary search on a sorted array, then return how many compares it took to find the user-input values.

int binarySearch(int arr[], int numelems, int value)
    {
        int first = 0, last = numelems - 1, middle, position = -1;
        bool found = false;
        int count = 0;
        while (!found && first <= last)
        {

            middle = (first + last) / 2;
            if (arr[middle] == value)
            {
                found = true;
                position = middle;
                count++;
            }
            else if (arr[middle] > value)
            {
                last = middle - 1;
                count++;
            }
            else
            {
                first = middle + 1;
                count++;
            }
        }
        return count;
    }

Below is the result I get when I call the function to search the number "38". (The result is correct).

enter image description here

I am trying to edit this function so it can also print out the number of compares even if the user-input number does not exist in the array.

So, ideally, if I try to search for the number “24”, the program should print out something like this:

The value 24 does not exist in the array.
It took 5 compares to reach the conclusion. 

Somehow I can't quite figure out how to do it... I tried to add an if-statement outside of the while loop, like below

int binarySearch(int arr[], int numelems, int value)
{
    int first = 0, last = numelems - 1, middle, position = -1;
    bool found = false;
    int count = 0;
    while (!found && first <= last)
    {
        middle = (first + last) / 2;
        if (arr[middle] == value)
        {
            found = true;
            position = middle;
            count++;
        }
        else if (arr[middle] > value)
        {
            last = middle - 1;
            count++;
        }
        else if (arr[middle] < value)
        {
            first = middle + 1;
            count++;
        }
    }
    if (found = false)
    {
        cout << "Value not found.";
    }
    return count;
}

I am not sure how to print out the count even the program didn't find the number, so I simply wrote a cout statement "Value not found." for trial, but even that's not working. If I run the code, this is the result I get

enter image description here

Upvotes: 0

Views: 115

Answers (1)

P.P
P.P

Reputation: 121397

You could simply add an if statement before return, like:

    if (!found)
    {
        cout << "The value " << value << " not found.\n";
    }

Or you could return two values with std::pair (whether the value is found and the count). Based on that, you could print the result at the call site.

Upvotes: 2

Related Questions