Binary search efficiently searches for a specific element in a sorted array or list. It follows a divide-and-conquer approach, repeatedly dividing the search space in half until it finds the target element or determines that the element is not present in the array.

Working of Binary Search Algorithm

Here’s a simple explanation of how binary search works and an implementation in C++:

1. Initialization: The algorithm begins by defining two pointers, left and right, which represent the current search interval. Initially, left is set to the first element of the array, and right is set to the last element.
2. Midpoint Calculation: Find the midpoint between left and right as mid by calculating mid = (left + right) / 2.
3. Comparison: Compare the element at the mid index with the target value.
   • If the element at mid is equal to the target, you’ve found the desired element, and the search terminates.
   • If the element at mid is greater than the target, update right to mid - 1 to eliminate the right half of the search interval.
   • If the element at mid is less than the target, update left to mid + 1 to eliminate the left half of the search interval.
4. Repeat: Repeat steps 2 and 3 until either the target element is found, or left is greater than right, indicating that the element is not in the array.

C++ Implementation of Binary Search

Here’s a simple C++ implementation of binary search for searching a target element in a sorted array:

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Element found at index 'mid'
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return -1; // Element not found in the array
}

int main() {
    std::vector<int> sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 5;

    int result = binarySearch(sortedArray, target);

    if (result != -1) {
        std::cout << "Element " << target << " found at index " << result << std::endl;
    } else {
        std::cout << "Element " << target << " not found in the array." << std::endl;
    }

    return 0;
}

This code defines a binarySearch function that takes a sorted vector and a target value as input and returns the index of the target element if found or -1 if not found. The main function demonstrates how to use the binary search function to search for a target value in a sorted array.

The provided C++ code performs a binary search for the target value 5 in the sorted array {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Since 5 is present in the array, the code will output the following:

Complexity Analysis

The time complexity and space complexity of the BS algorithm are as follows:

Time Complexity: The algorithm has a time complexity of O(log n), where “n” is the number of elements in the sorted array. This means that as the size of the input (the array) increases, the time it takes to perform a binary search grows logarithmically. This algorithm is highly efficient, especially when dealing with large datasets, as it can quickly narrow down the search space.

Space Complexity: The space complexity of the algorithm is O(1), which means it requires a constant amount of additional memory space regardless of the size of the input array. This is because binary search typically uses only a few variables (e.g., left, right, mid) to keep track of the search interval, and these variables do not depend on the size of the input array. We consider binary search an in-place algorithm with low memory usage.

In conclusion, binary search is a highly efficient algorithm for searching sorted arrays. It utilizes a divide-and-conquer approach to quickly locate specific elements. This method significantly reduces the number of comparisons required, making it a valuable tool for finding items in large datasets.

Do you know about the algorithm header file in C++ and how it makes the sorting 10x easier? Learn More