Welcome to today's lesson! We're diving into Binary Search, a clever technique for locating specific elements within a sorted list. We can find the targeted item by repeatedly dividing the search interval in half. It's akin to flipping through a dictionary — instead of going page by page, you'd start in the middle, then narrow down the section in half until you find your desired word.

Binary Search begins at the midpoint of a sorted list, halving the search area at each step until it locates the target. For example, if looking for the number 8 in a sorted list ranging from 1 to 10, we would start at 5. Since 8 is larger than the midpoint, we narrow the search to the second half of the list, leaving us with numbers 6 to 10. In this new sublist, the middle number is 8, and thus, we've found our target. This efficient approach significantly reduces the number of comparisons needed compared to a linear search.

Let's see how Binary Search can be implemented in C++, taking a recursive approach. This process involves a function calling itself — with a base case in place to prevent infinite loops—and a recursive case to solve smaller parts of the problem.

C++
Copy to clipboard
1#include <iostream>
2#include <vector>
3
4int BinarySearch(const std::vector<int>& arr, int start, int end, int target)
5{
6    if (start > end) return -1; // Base case
7    
8    int mid = start + (end - start) / 2; // Find the midpoint
9    
10    if (arr[mid] == target) return mid; // Target found
11    
12    if (arr[mid] > target) // If the target is less than the midpoint
13        return BinarySearch(arr, start, mid - 1, target); // Search the left half
14        
15    return BinarySearch(arr, mid + 1, end, target); // Search the right half
16}
17
18// Example usage
19int main() {
20    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
21    int target = 8;
22    int result = BinarySearch(arr, 0, arr.size() - 1, target);
23    
24    if (result != -1) {
25        std::cout << "Element found at index " << result << std::endl;
26    } else {
27        std::cout << "Element not found in the array." << std::endl;
28    }
29    return 0;
30}

In this C++ code, the base case is defined first. If the start index is greater than the end index, it indicates the search area is exhausted, resulting in a -1 return. The code then locates the midpoint. If the midpoint equals our target, it’s returned. Depending on whether the target is less or more than the midpoint, the search continues within the left or right half, respectively.

You can also implement the Binary Search algorithm iteratively using a while loop. Here is the C++ code for the iterative approach.

C++
Copy to clipboard
1#include <iostream>
2#include <vector>
3
4int BinarySearch(const std::vector<int>& arr, int target)
5{
6    int start = 0;
7    int end = arr.size() - 1;
8
9    while (start <= end)
10    {
11        int mid = start + (end - start) / 2;
12        if (arr[mid] == target) return mid;
13
14        if (arr[mid] < target)
15        {
16            start = mid + 1;
17        }
18        else
19        {
20            end = mid - 1;
21        }
22    }
23    return -1;
24}
25
26// Example usage
27int main() {
28    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
29    int target = 8;
30    int result = BinarySearch(arr, target);
31    
32    if (result != -1) {
33        std::cout << "Element found at index " << result << std::endl;
34    } else {
35        std::cout << "Element not found in the array." << std::endl;
36    }
37    return 0;
38}

Instead of dividing the array recursively, this code uses a while loop, which continues until the start index is equal to or less than the end index. The middle element is found the same way as in the recursive approach. If the target is equal to this middle element, we have found our target. On the other hand, if the target is greater than the middle element, we adjust the start index to be one position after the middle index. However, if the target is less than the middle element, we adjust the end index to be one position before the middle index.

Both the recursive and iterative versions of the Binary Search algorithm have a time complexity of O(log(n)), making them both very efficient.

However, the iterative version generally uses less memory space than the recursive one. Every recursive call in C++, like in most languages, adds a layer onto the system call stack, which stores information about active subroutines in a program. If the recursion gets too deep, it could result in stack overflow errors.

On the upside, some developers find recursive code easier to understand and debug because it often leads to simpler and cleaner code.

Finally, the choice between recursion and iteration can depend on the specifics of the problem being tackled, the performance characteristics of the specific system you're working on, and personal or team preferences. Both methods have their place in a programmer's toolkit.

Binary Search is a smart method for locating specific items within a sorted list. By repeatedly narrowing down the search area, it finds the target until the search area is reduced to zero. The key to mastering these concepts lies in practice. Starting with straightforward tasks, we will gradually navigate toward more complex problems that showcase the strength of Binary Search. Great job!