Binary search is an efficient algorithm for finding an element in a sorted array. The algorithm works by repeatedly dividing the search interval in half and comparing the target value to the middle element of the array. If the target value is equal to the middle element, the search is successful. If the target value is less than the middle element, the search continues on the left half; otherwise, it continues on the right half. This process continues until the target value is found or the search interval is empty.

Binary Search Algorithm

Iterative Implementation

Here's how you can implement binary search iteratively in C++:

#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; // Target found
        }
        if (arr[mid] < target) {
            left = mid + 1; // Search in the right half
        } else {
            right = mid - 1; // Search in the left half
        }
    }
    return -1; // Target not found
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;
    int result = binarySearch(arr, target);

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

    return 0;
}

Recursive Implementation

Binary search can also be implemented recursively:

#include <iostream>
#include <vector>

int binarySearchRecursive(const std::vector<int>& arr, int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Target found
        }
        if (arr[mid] < target) {
            return binarySearchRecursive(arr, mid + 1, right, target); // Search in the right half
        } else {
            return binarySearchRecursive(arr, left, mid - 1, target); // Search in the left half
        }
    }
    return -1; // Target not found
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;
    int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);

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

    return 0;
}

Time Complexity

The time complexity of binary search is \(O(\log n)\), where \(n\) is the number of elements in the array. This is because the search interval is halved with each iteration or recursive call.

Space Complexity

• Iterative implementation: The space complexity is \(O(1)\) because it uses a constant amount of additional space.
• Recursive implementation: The space complexity is \(O(\log n)\) due to the recursion stack.

Summary

• Binary search is an efficient algorithm for finding elements in sorted arrays.
• Iterative and recursive implementations are both common.
• The algorithm has a time complexity of \(O(\log n)\), making it much faster than linear search for large arrays.

Feel free to ask if you need further details or examples!

Upper Bound