One-Dimensional Binary Search

Binary search efficiently locates a target value within a sorted sequence by repeatedly halving the search interval. The algorithm evaluates the middle element; if it matches the target, the search concludes. If the middle element is less than the target, the search continues in the right subarray. Conversely, if the middle element is greater, the left subarray is examined. This process repeats on the shrinking interval until the element is found or the interval is empty.

Interval boundaries dictate the loop condition and pointer updates:

• Left-Closed, Right-Closed [low, high]: The initial high index is size - 1. The loop continues while low <= high. When adjusting boundaries, the middle index must be excluded: low = mid + 1 or high = mid - 1.
• Left-Closed, Right-Open [low, high): The initial high index is size. The loop continues while low < high. When adjusting, the right boundary includes the middle index: high = mid, while the left excludes it: low = mid + 1.

Below is an implementation using the left-closed, right-closed interval approach:

int fetchIndex(const std::vector<int>& data, int query) {
    int lo = 0, hi = data.size() - 1;
    while (lo <= hi) {
        int center = lo + (hi - lo) / 2;
        if (data[center] == query) return center;
        if (data[center] < query) lo = center + 1;
        else hi = center - 1;
    }
    return -1;
}

Two-Dimensional Matrix Search

When searching in a matrix where each row is sorted left-to-right and each column is sorted top-to-bottom, a staircase search algorithm is highly effective. Starting from the top-right corner, the algorithm compares the current element to the target. If the target is smaller, move left to decrease the value. If the target is larger, move down to increase the value.

bool locateTarget(const std::vector<std::vector<int>>& grid, int goal) {
    if (grid.empty() || grid[0].empty()) return false;
    int r = 0, c = grid[0].size() - 1;
    while (r < grid.size() && c >= 0) {
        if (grid[r][c] == goal) return true;
        if (grid[r][c] < goal) ++r;
        else --c;
    }
    return false;
}

Optimized Two-Dimensional Search

The standard staircase search can be optimized by starting from the middle row of the rightmost column instead of the top row. By comparing the target with this central element first, we can eliminate half of the rows from the initial search space. If the target is greater than the middle element, the search begins from the row directly below it, skipping the entire upper half. If the target is smaller, the search proceeds from the first row as usual.

bool locateTargetOptimized(const std::vector<std::vector<int>>& grid, int goal) {
    if (grid.empty() || grid[0].empty()) return false;
    int totalRows = grid.size();
    int lastCol = grid[0].size() - 1;
    int startRow = totalRows / 2;

    if (grid[startRow][lastCol] == goal) return true;

    if (grid[startRow][lastCol] < goal) {
        startRow++;
    } else {
        startRow = 0;
    }

    int r = startRow, c = lastCol;
    while (r < totalRows && c >= 0) {
        if (grid[r][c] == goal) return true;
        if (grid[r][c] < goal) ++r;
        else --c;
    }
    return false;
}