Binary Search in a 2D Matrix

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int row = matrix.size();       // Number of rows
    int col = matrix[0].size();    // Number of columns

    int start = 0;                 // Start index of the 1D array representation
    int end = row * col - 1;       // End index of the 1D array representation

    // Perform binary search
    int mid = start + (end - start) / 2;

    while (start <= end) {
        // Convert the 1D mid index back into 2D coordinates
        int element = matrix[mid / col][mid % col];

        if (element == target) {
            return true;  // Target found
        }

        if (element < target) {
            start = mid + 1;  // Move to the right half
        } else {
            end = mid - 1;    // Move to the left half
        }

        // Recalculate the mid index for the next iteration
        mid = start + (end - start) / 2;
    }

    return false;  // Target not found
}

Example:

vector<vector<int>> matrix = {
    {1, 3, 5, 7},
    {10, 11, 16, 20},
    {23, 30, 34, 60}
};

int target = 16;
bool found = searchMatrix(matrix, target);

Step-by-Step Example:

Given the matrix:

1   3   5   7
10  11  16  20
23  30  34  60

We want to find 16.

1. Initial Values:
   • row = 3, col = 4, start = 0, end = 11 (since 3 * 4 - 1 = 11), mid = (0 + 11) / 2 = 5.
2. First Iteration:
   • mid = 5
   • Convert mid into 2D index: matrix[5 / 4][5 % 4] = matrix[1][1] = 11.
   • 11 < 16, so move to the right half by setting start = mid + 1 = 6.
3. Second Iteration:
   • mid = (6 + 11) / 2 = 8
   • Convert mid into 2D index: matrix[8 / 4][8 % 4] = matrix[2][0] = 23.
   • 23 > 16, so move to the left half by setting end = mid - 1 = 7.
4. Third Iteration:
   • mid = (6 + 7) / 2 = 6
   • Convert mid into 2D index: matrix[6 / 4][6 % 4] = matrix[1][2] = 16.
   • 16 == 16, target found!