Binary Search Algorithm in C++

How does the Binary Search Algorithm work?

Search algorithms are essential for efficiently finding specific data within large datasets. Whether it’s looking for a particular number in a list or locating a file in a directory, search algorithms help reduce the time it takes to find information.

The Binary Search algorithm is a divide-and-conquer algorithm used to find an element within sorted datasets. Systematically halving the search range reduces the time complexity, making it significantly faster than linear search for large collections.

Binary search is like finding a specific page in a book. Instead of starting at the beginning and flipping through every page, you open the book roughly in the middle, check if you’re too far ahead or behind, and then focus on half where the page might be. By repeatedly halving the search area, binary search quickly narrows down the possibilities, making it much faster than checking each page individually.

In this article, we will study the principles of binary search and implement it iteratively and recursively in C++.

We’ll begin with the iterative approach, as it is more intuitive and easier to grasp for beginners.

Let’s explore how Binary Search works in practice with this method.

How to Implement Iterative Binary Search in C++?

Binary search works on a dataset that is sorted in a specific order, either ascending (from smallest to largest) or descending (from largest to smallest). It starts by checking the middle element of the range. If the target value matches the middle element, the search ends. If the target is smaller than the middle element, the search continues in the left half; if it is larger, the search continues in the right half. This process repeats until the target is found or there are no more elements to check.

Now, let’s walk through the steps involved in the iterative implementation of the binary search algorithm.

Steps for Iterative Binary Search Algorithm

1. Define the Search Range: Start with two pointers, low (at the beginning of the array) and high (at the end of the array), to confine the search range to [low, high].

2. Calculate the Middle Index: Find the middle index of the current range using the formula:

   $\text{mid} = \text{low} + \frac{\text{high} - 
       \text{low}}{2}$

   This approach prevents overflow issues by avoiding the direct addition of low and high, which could exceed the maximum value allowed by the data type and lead to incorrect calculations.

3. Compare the Middle Element:

   • If the middle element matches the target, return mid as its position.
   • If the middle element is lower than the target, search in the right half by setting low to mid + 1.
   • If the middle element exceeds the target, search in the left half by setting high to mid - 1.

4. Repeat Until the Range is Exhausted: Continue steps 2 and 3 until the low pointer exceeds the high pointer.

If this happens without finding the target, the search concludes that the target is not present in the dataset.

Let’s first introduce these steps into pseudocode before diving into the implementation.

Pseudocode for Iterative Binary Search Algorithm

BinarySearch(arr, target):   
    low = 0   
    high = size of arr - 1   

    while low <= high:   
        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  // Target not found  

The following implementation translates the pseudocode into working C++ code, demonstrating how binary search can be applied iteratively.

Implementation of Iterative Binary Search Algorithm

#include <iostream> 
#include <vector> 

using namespace std; 

int binarySearchIterative(const vector<int>& arr, int target) { 

// Initialize pointers for the start and end of the array  
int low = 0, high = arr.size() - 1; 

while (low <= high) { 
  
  // Calculate the middle index 
  int mid = low + (high - low) / 2; 

  // If the middle element is the target, return its index 
  if (arr[mid] == target) { 
   return mid; 
  } 

  // If the target is greater than the middle element, search the right half 
  else if (arr[mid] < target) { 
   low = mid + 1; 
  } 

  // If the target is less than the middle element, search the left half 
  else { 
   high = mid - 1; 
  } 
} 

// Return -1 if the target is not found in the array 
return -1; 
}   

int main() { 
// Sorted array of integers 
vector<int> data = {2, 3, 5, 7, 11, 13, 17}; 

int target = 7;  // Element to search for 
  
// Call binary search and store the result 
int result = binarySearchIterative(data, target); 

// Output the result based on whether the element was found 
if (result != -1) { 
  cout << "Element found at index " << result << endl; 
} else { 
  cout << "Element not found. Index: " << result << endl; 
} 

return 0; 
} 

The iterative version of binary search uses loops to reduce the search range gradually. It can also be implemented recursively, which more naturally highlights the divide-and-conquer approach.

Let’s take a look at the recursive implementation of binary search.

How to Implement Recursive Binary Search in C++

The recursive approach follows the same principles as the iterative one, but with a key difference - it employs the power of recursion to break the problem down into smaller, more manageable subproblems.

This approach embodies the divide and conquer strategy, where the problem is repeatedly divided into halves. The solution is found by solving these smaller subproblems through self-calls, narrowing the search boundaries with each step.

Steps for Recursive Binary Search Algorithm

Here’s how it works:

1. Base Case: If the low pointer exceeds the high pointer, the search range is exhausted, and the target is not present in the dataset. Return -1 to indicate failure.

2. Calculate the Middle Index: Compute the middle index using the formula:

   $\text{mid} = \text{low} + \frac{\text{high} - \text{low}}{2}$

3. Compare the Middle Element:

   • If the middle element matches the target, return the middle index as the target’s position.

   • If the middle element is less than the target, recursively search the right half by setting low to mid + 1.

   • If the middle element is greater than the target, recursively search the left half by setting high to mid – 1.

4. Repeat Through Recursion:

   The recursion continues, halving the search space with each call until the base case is met or the target is found.

With these steps in mind, let’s look at the pseudocode for this approach.

Pseudocode for Recursive Binary Search Algorithm

BinarySearch(arr, low, high, target):   
    if low > high:   
        return -1  // Base case: Target not found   

    mid = low + (high - low) / 2   
    if arr[mid] == target:   
        return mid   
    else if arr[mid] < target:   
        return BinarySearch(arr, mid + 1, high, target)   
    else:   
        return BinarySearch(arr, low, mid - 1, target)   

Implementation of Recursive Binary Search Algorithm

#include <iostream>
#include <vector>

using namespace std;

int binarySearchRecursive(const vector<int>& arr, int low, int high,
                          int target) {
 // Base case: If the search range is invalid, the target is not found
 if (low > high) {
  return -1;  // Target not found
 }

 // Calculate the middle index of the current search range
 int mid = low + (high - low) / 2;

 // If the middle element is the target, return its index
 if (arr[mid] == target) {
  return mid;
 }

 // If the target is greater than the middle element, search in the right half
 else if (arr[mid] < target) {
  return binarySearchRecursive(arr, mid + 1, high,
                               target);  // Recursive call on the right half
 }

 // If the target is less than the middle element, search in the left half
 else {
  return binarySearchRecursive(arr, low, mid - 1,
                               target);  // Recursive call into the left half
 }
}

int main() {
 // Sorted array of integers

 vector<int> data = {2, 3, 5, 7, 11, 13, 17};

 int target = 13;  // Element to search for

 // Call the recursive binary search and store the result

 int result = binarySearchRecursive(data, 0, data.size() - 1, target);

 if (result != -1) {
  cout << "Element found at index " << result << endl;

 } else {
  cout << "Element not found. Index: " << result << endl;
 }

 return 0;
}

The output of the program will be:

Element found at index 5 

Now that we have covered both iterative and recursive implementations of binary search in C++, let’s analyze the binary search algorithm’s performance by finding the time and space complexity.

Analyzing Time and Space Complexity of Binary Search

Binary search works by halving the search space at each step. If the initial size is n, after the first step, the search space is n/2, then n/4, n/8, and so on. This continues until only one element remains, which happens when the search space is reduced to 1.

The number of steps it takes to reach 1 is the number of times n can be divided by 2, which is log₂(n). Since each step takes constant time, the overall time complexity for binary search is O(log n).

In terms of space complexity, the iterative approach requires O(1) space since it uses no additional memory, while the recursive approach has a space complexity of O(log n) due to the call stack.

Next, let’s look at the advantages and disadvantages of binary search in C++.

Advantages and Disadvantages of Binary Search in C++

Advantages of Binary Search

• Faster than linear search for large datasets.
• Easy to implement and debug.

Disadvantages of Binary Search

• Requires sorted data.
• Preprocessing (sorting) can be costly.

Binary search doesn’t work well with data that changes often because sorting the data before searching takes longer than the search itself.

Now that we have covered the binary search algorithm, let’s explore some of its common applications.

Applications of Binary Search Algorithm

Binary search has a wide range of uses, including:

• Finding Lower Bound and Upper Bound: Binary Search can find the positions where an element should be inserted in a sorted array.
  • Lower Bound: The position of the first occurrence of the target or where it can be inserted to maintain order.
  • Upper Bound: The position just after the last occurrence of the target or where it can be inserted to maintain order.
• Square Root Approximation: Binary Search can approximate a number’s square root by narrowing down the range and checking the square of the middle value until it’s close enough.
• Finding the minimum of a maximum: Binary Search is useful for problems that require finding the minimum of a maximum (or vice versa). It efficiently narrows down the possible values by halving the search space at each step, making it ideal for optimization problems with large ranges or continuous values.

Concept Review and Next Steps

This article covered the basics of binary search, including its iterative and recursive implementations and applications. Due to its efficiency, Binary search is crucial for searching through sorted datasets and solving many problems.

To deepen your understanding, try applying Binary Search to different types of problems, such as those involving sorted data. You can also explore combining Binary Search with other algorithms to improve efficiency in more complex scenarios.

To dive deeper into search algorithms and build a strong foundation in C++, explore Codecademy’s Learn C++ course, where you can practice coding exercises and master key C++ concepts.