Binary Search Algorithms Explained using C++

Binary search is one of the most fundamental and important algorithms in computer science. It allows us to efficiently search for an element in a sorted array, by repeatedly dividing the search interval in half. On average, binary search will require only O(log n) comparisons to find the target element, making it much faster than linear search which requires O(n) comparisons in the worst case.

In this post, we‘ll take an in-depth look at how the binary search algorithm works and implement it using C++. Whether you‘re a coding beginner or an experienced programmer, understanding binary search is an essential skill that will serve you well. Let‘s jump right in!

How Binary Search Works

The basic idea behind binary search is to maintain a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. Initially, the search space is the entire sequence. At each step, we compare the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, we can then eliminate half of the search space. By doing this repeatedly, we will eventually be left with a search space consisting of a single element, which hopefully is the target value.

For binary search to work, the data must be sorted. If not, we would have to sort it first, which would take O(n log n) time before even starting the search.

To illustrate how binary search works, let‘s walk through a simple example of searching for the value 7 in a sorted array:

int arr[] = {1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71};

We start by defining two pointers, low and high, which initially point to the first and last elements respectively. So low is 0 and high is 16.

The binary search algorithm now proceeds as follows:

1. Find the middle element. This is at index (low + high) / 2 = 8, which is 14.
2. Compare 14 with the target value 7. Since 14 > 7, we can discard all elements to the right of 14. We update high to be one less than the middle index, so high becomes 7.
3. Find the new middle element between low (0) and high (7). This is at index 3, which is 6.
4. Compare 6 with 7. Since 6 < 7, we update low to be one more than the middle index. So low becomes 4.
5. The middle element between 4 and 7 is at index 5, which is 8.
6. We compare 8 with 7. Since 8 > 7, we update high to be 4.
7. Now low and high both point to index 4. The middle element is also at index 4, which is 7.
8. We‘ve found the target value 7 at index 4. The search ends.

By discarding half of the remaining elements at each step, binary search narrows down the search space very quickly, making it much more efficient than linear search for large sorted arrays.

Binary Search Algorithm

Now that we understand how binary search works, let‘s formalize the algorithm in pseudocode:

function binarySearch(arr, target):
    low = 0
    high = arr.length - 1
while low <= high:
    mid = (low + high) / 2

    if arr[mid] == target:
        return mid
    else if arr[mid] < target: 
        low = mid + 1
    else:
        high = mid - 1

return -1 // target not found
The key variables used are:

low: The index of the first element in the current search space. Initially 0.
high: The index of the last element in the search space. Initially the last index.
mid: The index of the middle element, calculated as (low + high) / 2. 

We use a while loop to repeatedly divide the search space in half until the target is found or the search space is empty (meaning the target is not in the array). Inside the loop, we compare the middle element arr[mid] to the target. If they are equal, we‘ve found the target and return its index. If the middle element is less than the target, we update low to search the right half of the array. Otherwise, we update high to search the left half.
If the while loop terminates without finding the target, that means the target is not present in the array. In this case, we return -1 to indicate the target was not found.
The time complexity of binary search is O(log n) in both the average and worst cases, since we divide the search space in half at each step. The space complexity is O(1), as only a few variables are used regardless of the size of the input.
Implementing Binary Search in C++
Implementing binary search in C++ is straightforward. Here‘s a complete program that demonstrates the binary search algorithm:
#include 
using namespace std;
int binarySearch(int arr[], int n, int target) {
int low = 0;
int high = n - 1;
while (low <= high) {
    int mid = low + (high - low) / 2;

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        low = mid + 1;
    else
        high = mid - 1;
}

return -1;
}
int main() {

int arr[] = {1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71};

int n = sizeof(arr) / sizeof(arr[0]);

int target = 7;
int index = binarySearch(arr, n, target);

if (index != -1)
    cout << "Element " << target << " found at index " << index << endl;
else
    cout << "Element not found in the array" << endl;

return 0;
}
The binarySearch() function implements the algorithm exactly as described in the pseudocode. In main(), we first create a sorted array and define the target value. We then call binarySearch() and pass the array, its size, and the target. The returned index is stored and used to print the result.
Note that when calculating the middle index, we use mid = low + (high – low) / 2 instead of the more obvious (low + high) / 2. This is to avoid potential integer overflow if low + high is greater than the maximum possible int value.
We can also implement binary search recursively:
int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high)
        return -1;
int mid = low + (high - low) / 2;

if (arr[mid] == target)
    return mid;
else if (arr[mid] < target)
    return binarySearchRecursive(arr, mid + 1, high, target);
else
    return binarySearchRecursive(arr, low, mid - 1, target);
}
The recursive version follows the same logic, but uses recursive calls to search the left or right half of the array instead of updating low and high in a loop. The base case is when low > high, indicating the search space is empty and the target was not found.
The recursive approach is more concise but has a space complexity of O(log n) due to the recursive calls on the call stack. The iterative version is usually preferred in practice.
Analyzing Binary Search
Let‘s prove that binary search indeed has a time complexity of O(log n). At each step, we divide the search space in half. In the worst case, we will continue doing this until there is only one element left.
Suppose we start with an array of size n. After the first iteration, the size of the search space will be n/2. After the second iteration, it will be n/4. After the third iteration n/8, and so on. In general, after i iterations, the search space will have size n / 2^i.
We stop when the search space has size 1, so we want to find the smallest i such that:

n / 2^i = 1
Solving for i, we get:

n = 2^i

i = log(n)
Therefore, binary search will perform at most log(n) iterations. At each iteration, we perform a constant amount of work (comparing the middle element to the target). So the time complexity of binary search is O(log n).
Compare this to linear search, which has a time complexity of O(n) in the worst case since it may have to scan through all n elements to find the target. For large arrays, binary search will be much faster.
However, binary search requires the input data to be sorted. If the data is not already sorted, we need to sort it first, which takes O(n log n) time. So binary search is only efficient if we plan to perform many searches on the same data or if the data is already sorted for other reasons.
Binary search also requires random access to elements in the array by their index. This makes it unsuitable for data structures like linked lists where accessing elements by index takes linear time. In practice, binary search is most commonly used on arrays and array-like data structures that provide fast random access.
Binary Search Variants
The C++ Standard Template Library (STL) provides two variants of binary search: lower_bound and upper_bound. These functions are defined in the  header.
lower_bound returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e., greater than or equal to) the target value. If all elements in the range compare less than the target value, the returned iterator points to last, the end of the range.
upper_bound returns an iterator pointing to the first element in the range [first, last) that is greater than the target value. If no such element exists, the returned iterator points to last.
Here‘s an example of how to use lower_bound and upper_bound:
#include 
#include 
using namespace std;
int main() {
int arr[] = {1, 3, 4, 6, 7, 8, 10, 13, 14, 14, 18, 19, 21, 24, 37, 40, 45, 71};
int n = sizeof(arr) / sizeof(arr[0]);
auto lower = lower_bound(arr, arr + n, 14);
auto upper = upper_bound(arr, arr + n, 14);

cout << "lower_bound for 14: " << (lower - arr) << endl;
cout << "upper_bound for 14: " << (upper - arr) << endl;
cout << "Occurrences of 14: " << (upper - lower) << endl;

return 0;
}
This code will output:
lower_bound for 14: 8
upper_bound for 14: 10
Occurrences of 14: 2

lower_bound finds the first occurrence of 14 at index 8, while upper_bound finds the first element greater than 14, which is at index 10. The difference between these iterators gives the number of occurrences of 14 in the array.
Binary search can also be used to solve problems beyond just searching for a specific value. For example:

Finding the first or last occurrence of a value in a sorted array
Determining the index where a target value should be inserted to maintain a sorted array
Searching for the square root or cube root of a number
Optimizing guessing games where feedback is provided (e.g., "too high", "too low")

Whenever you have a problem where the search space can be divided in half based on some condition, consider if binary search could be applied to solve it efficiently.
Conclusion
Binary search is a powerful algorithm that every programmer should know. Its key advantages are:

It‘s extremely efficient, with a time complexity of O(log n).
It‘s simple to implement and easy to understand.
It can be used to solve a variety of search-related problems.

However, it‘s important to remember that binary search requires the input data to be sorted. If the data is unsorted, you‘ll need to sort it first before you can apply binary search.
We‘ve covered the basics of how binary search works, implemented it in C++, analyzed its time and space complexity, and discussed some variants and related problems. I encourage you to implement binary search yourself and experiment with it on different inputs to solidify your understanding.
With binary search in your toolkit, you‘ll be able to efficiently solve many search problems that come your way. Happy coding!


	
Related