Binary search operates on sorted sequences to locate specific values efficiently. Unlike linear scanning which requires O(n) time, binary search reduces the search space by half at each step, achieving O(log n) complexity. This logarithmic growth remains manageable even for massive datasets, such as arrays containing millions of elemants.

Implemantation Strategy

The algorithm maintains a range defined by start and end indices. At each iteration, it calculates the midpoint and compares the target value against the element at that position. If the values match, the search terminates successfully. Otherwise, the boundary is adjusted based on whether the target is smaller or larger than the current midpoint.

To prevent integer overflow when calculating the midpoint (where left + right might exceed standard limits), use the formula mid = left + (right - left) / 2.

#include <iostream>
#include <vector>
#include <algorithm>

void findTarget(const std::vector<int>& dataset, int target) {
    int start_idx = 0;
    int end_idx = static_cast<int>(dataset.size()) - 1;
    int mid_idx = start_idx;
    bool found = false;

    while (start_idx <= end_idx && !found) {
        mid_idx = start_idx + (end_idx - start_idx) / 2;
        
        if (dataset[mid_idx] == target) {
            std::cout << "Found index: " << mid_idx << std::endl;
            found = true;
        } else if (target > dataset[mid_idx]) {
            start_idx = mid_idx + 1;
            mid_idx = start_idx + (end_idx - start_idx) / 2;
        } else {
            end_idx = mid_idx - 1;
            mid_idx = start_idx + (end_idx - start_idx) / 2;
        }
    }

    if (!found) {
        std::cout << "Target not found in sequence." << std::endl;
    }
}

Handling Duplicate Elements

Standard binary search returns any valid index for duplicates. To retrieve the full range [lower_bound, upper_bound] of identical values, two specialized passes are required.

Locating the Lower Bound

Find the first occurrence by narrowing the range whenever the middle element is greater than or equal to the target. If data[mid] >= target, the potential leftmost index could be at mid or earlier.

Locating the Upper Bound

Find the last occurrence by adjusting logic when the middle element is less than or equal to the target. If data[mid] <= target, the potential rightmost index could be at mid or later.

int findLeftBound(const std::vector<int>& dataset, int target) {
    int low = 0;
    int high = static_cast<int>(dataset.size()) - 1;
    
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (dataset[mid] >= target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int findRightBound(const std::vector<int>& dataset, int target) {
    int low = 0;
    int high = static_cast<int>(dataset.size()) - 1;
    
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (dataset[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return high;
}

Application: Continuous Domain Approximation

Binary search applies to continuous functions where monotonicity holds, such as finding square roots.

To calculate √x, search within a floating-point range. The condition checks if mid * mid equals x. Since exact equality is rare with doubles, termination depends on the precision threshold (e.g., difference between bounds < 0.0001).

#include <cmath>

void approximateSqrt(double number) {
    double lower = 0.0;
    double upper = number;
    double mid;

    if (number < 1.0) { 
        lower = number; 
        upper = 1.0; 
    }

    while (upper - lower > 1e-5) {
        mid = (lower + upper) / 2.0;
        if (mid * mid > number) {
            upper = mid;
        } else {
            lower = mid;
        }
    }
    std::cout << "Approximate Root: " << mid << std::endl;
}

Application: Resource Allocation

Problems involving partitioning resources often rely on monotonic relationships.

Water Capacity Problem: Determining height given volume requires checking area formulas. As height increases, area generally increases, allowing binary search on height h.

Material Cutting: Given a set of stick lengths, determine the maximum length obtainable for k pieces. Shorter cut lengths yield more pieces; longer cuts yield fewer. This inverse relationship allows searching for the optimal length.

int countPieces(const std::vector<int>& sticks, int cutLength) {
    int total = 0;
    for (const auto& stick : sticks) {
        total += stick / cutLength;
    }
    return total;
}

int solveOptimization(std::vector<int>& sticks, int requiredK) {
    int max_stick = 0;
    for (int s : sticks) max_stick = std::max(max_stick, s);

    int low = 1;
    int high = max_stick;
    int best_len = 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (countPieces(sticks, mid) >= requiredK) {
            best_len = mid;
            low = mid + 1; // Try for a longer piece
        } else {
            high = mid - 1; // Too long, shorten
        }
    }
    return best_len;
}

Fast Exponentiation

Calculating a^b via multiplication iteratively takes O(b) time. Fast exponentiation leverages divide-and-conquer to achieve O(log b). The core logic relies on properties of exponants:

• If b is even: a^b = (a^(b/2))^2
• If b is odd: a^b = a * a^(b-1)

This method significantly reduces computation steps for large powers.

Iterative Approach

long long fastPowIter(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    return result;
}

Recursive Approach

long long fastPowRec(long long base, long long exp) {
    if (exp == 0) return 1;
    long long half = fastPowRec(base, exp / 2);
    if (exp % 2 == 0) {
        return half * half;
    } else {
        return half * half * base;
    }
}

Note: Always handle potential overflow by using long long types for intermediate calculations.