Efficient Binary Search Methods for 2D Matrices

Problem Statement

Given a matrix where:

• Integers in each row are sorted from left to right.

• The first integer of each row is greater than the last integer of the previous row.

We need to determine whether a target integer exists in this matrix.

You must write a solution in O(log(m * n)) time complexity.

Example →

[ [1, 3, 5],

[7, 10, 11],

[12, 14, 16] ]

If we are looking for 10, the function should return true. If we are looking for 6, the function should return false.

Implementation

function searchMatrix(matrix: number[][], target: number): boolean {
    let m = matrix.length;
    let n = matrix[0].length;

    let left = 0;
    let right = m * n - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let row = Math.floor(mid / n);
        let column = mid % n;

        let matrixMid = matrix[row][column];

        if (matrixMid > target) {
            right = mid - 1;
        } else if (matrixMid < target) {
            left = mid + 1;
        } else {
            return true;
        }
    }

    return false;
}

Explanation

Step 1: Initialization

• First, we find how many rows (m) and how many columns (n) are in the matrix.

• Then, we set two pointers:

  • left starts at the first element of the matrix (position 0).

  • right starts at the last element of the matrix (position m * n - 1).

Step 2: Binary Search Loop

• We enter a loop that keeps running as long as left is less than or equal to right.

• In each loop, we find the middle position (mid) between left and right.

  • mid = Math.floor((left + right) / 2)

• When we treat the 2D matrix like one long list (or array), we need to figure out which row and column a particular position belongs to.

  • For the row: Imagine you stretched out the matrix into one long line of numbers. To figure out which row a number is in, you divide the position (mid) by the number of columns (n). This gives you how many full rows are before that position.

    • row = Math.floor(mid / n)

Example: If mid = 7 and there are n = 3 columns, then:

• row = Math.floor(7 / 3) = 2, meaning the number is in the 2nd row (starting from row 0).

  • For the column: Now, to find out which column that number is in, you take the remainder when dividing mid by the number of columns (n). This remainder tells you how far along the row the number is.

• column = mid % n

Example: Using mid = 7 and n = 3 again:

• column = 7 % 3 = 1, meaning the number is in the 1st column (starting from column 0).Now, we compare the value at matrix[row][column] (let's call it matrixMid) with the target:

  • If matrixMid is greater than the target, we move right to mid - 1 to search the left half of the matrix.

  • If matrixMid is smaller than the target, we move left to mid + 1 to search the right half of the matrix.

  • If matrixMid equals the target, we return true because we have found the target.

Step 3: Target Not Found

• If the loop finishes and we haven't found the target, it means the target isn't in the matrix, so we return false.

---

Time Complexity

• The time complexity is O(log(m * n)), which means the search time grows slowly even if the matrix gets larger. This happens because each time, we cut the search space in half (thanks to binary search).

Space Complexity

• The space complexity is O(1), meaning we are using a constant amount of extra space, only a few variables, regardless of the matrix size.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase