So this is something we have all learned in a basic Computer Science course. However, I just wanted to write down a super simple implementation of Binary Search for people who are interested. As you should already know, Binary Search can only be done on a sorted array. This function will only give you the index of the target in the given array. When first calling it, pass 0 for left ptr and array.size() – 1 for the right ptr.
int binarySearch(vector<int>& array, int target, int leftPtr, int rightPtr)
{
int middle_index = (leftPtr + rightPtr) / 2;
int potentialMatch = array[middle_index];
if (target == potentialMatch)
{
return middle_index;
}
else if (target > potentialMatch)
{
return binarySearch(array, target, middle_index + 1, rightPtr);
}
else
{
return binarySearch(array, target, leftPtr, middle_index - 1);
}
}