Search for a target value in a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • 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.

Example:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

target = 11
Output: true

Binary Search:

the input matrix m x n could be considered as a sorted array of length m x n. So we can use Binary Search in the 2D matrix with a little trick to calculate the index of the mid element.

int pivot = left + (right-left)/2;
int pivotElement = matrix[pivot/width][pivot%width];

The following diagram is a pictorial representation of the logic to find the  mid element.

public boolean searchMatrix(int[][] matrix, int target) {

        int height = matrix.length;
        if (height == 0) return false;
        int width = matrix[0].length;

        int left = 0;
        int right = (height * width - 1);
        while (left <= right) {
            int pivot = left + (right - left) / 2;
            int pivotElement = matrix[pivot / width][pivot % width];
            if (target == pivotElement) {
                return true;
            } else {
                if (target > pivotElement) left = pivot + 1;
                else right = pivot - 1;
            }
        }
        return false;
}

Complexity Analysis

  • Time Complexity: O(log(mn)) since it’s a standard binary search.
  • Space Complexity: O(1).

Categories: Binary Search

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s