As a part of the STL, C++ comes pre-packaged with a binary search function as a part of the “algorithm” library. So why then would you bother making your own version that’ll likely be worse than the one already made for you? The answer is that figuring out how a binary search algorithm works is the first stepping stone towards implementing other more complex search algorithms which have not been so kindly written into the standard library for you.
Libraries and Function Definitions
The only library that you’ll need for this program is “iostream” for the purpose of getting user input and displaying the program results to the screen.
#include <iostream>
Once you’ve got the library included you’ll need to declare the binary search function, this will be what actually implements the algorithm for you. It takes the following three arguments: the array which the program is searching through, the size of said array, and the number the program is searching for.
int binarySearch(int numbers[], int arrsize, int userinput);
Binary Search Function
Once you’ve declared your binary search function you then need to define it. First you need to define variables for the smallest index in the array and the largest index in the array. No matter the array size the lowest index will always be zero and the largest is equal to the array size variable. You’ll also need a variable for the middle index of the array which shouldn’t be set to equal anything right now.
int low = 0; int high = arrsize; int mid;
Next you’ll need a while loop that’ll loop for as long as the low variable is smaller than the high variable. At the start of this loop the mid variable should be set to low plus high divided by two as this would be the middle index of the array.
while (low <= high)
{
mid = (low + high) / 2;
Now if that middle point is equal to the number we’re looking for then the function should return mid. If instead the number we’re looking for is bigger than the middle point low should be set equal to mid+1, this effectively removes the first half of the array from the equation as it will no longer be taken into account when the loop runs. If on the other hand the number we’re looking for is smaller than the middle point high should be set equal to mid-1, effectively removing the second half of the array from the equation instead. Lastly if the loop runs its course and yet still we can’t find the number we want just have the program return -1.
while (low <= high)
{
mid = (low + high) / 2;
if(userinput == numbers[mid])
{
return mid;
}
else if (userinput > numbers[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
Let’s move on to the program’s main function now.
Main Function
First you’re going to need to define an array of pre-sorted numbers, the size of this array doesn’t really matter as long as you don’t make it something silly like one hundred million numbers in length.
int main()
{
int a[] = {4, 16, 22, 54, 79, 97, 103, 120, 167, 195, 348};
After that you need to figure out what number the user wants to search the array for. Invalid input won’t break the program, the user will just be told later that whatever they asked for couldn’t be found.
int input;
std::cout << "Enter an integer: ";
std::cin >> input;
Once this is done you need to call the binary search function you made, pass the necessary variables into it and then set a new variable equal to its return value. Now the array and the user input are pretty simple to pass on but you might be wondering how to get the size of an array in C++. There is a function called “sizeof()” which will fetch the size of an array or array element in bytes. If you then get the byte size of the array as a whole and then divide it by the byte size of a single element that will leave you with the number of elements in an array.
int result = binarySearch(a, sizeof(a)/sizeof(a[0]), input);
Lastly you need to display this result to the user. If the return value of “binarySearch” is any value other than -1 that means the program successfully found the input somewhere in the array. Otherwise if it is -1 that means whatever the user was attempting to search for did not exist within the array.
if(result >= 0)
{
std::cout << input << " was found at index " << result << std::endl;
}
else
{
std::cout << input << " was not found. " << std::endl;
}
}
And with that you should have a functioning binary search algorithm!
Further Suggestions
Instead of hard coding in an array for the algorithm to search through you could instead have an array containing a random amount of random numbers instead. For a more difficult challenge you can try implementing a sorting algorithm into your program which would make sure that every array is sorted before being run through the binary search.
Good Luck!
Download the source code here.
If you have any questions or comments send them to me at nick@crumbsofcode.com
