Reputation: 139
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).
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
Upvotes: 0
Views: 115
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