Search a 2D Matrix

Description

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
Consider the following matrix:
[
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]
Given target = 3, return true.

Challenge
O(log(n) + log(m)) time
O(log(n) + log(m)) = O(log(mn))

Link

Lintcode_ladder

Method

1. Treat the 2D matrix as a sequence
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // write your code here
        if (matrix.empty()) {
            return false;
        }
        int rowlength = matrix[0].size();
        int start = 0;
        int end = matrix.size() * matrix[0].size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            // translate the row and col from sequence index 
            int row = mid / rowlength;
            int col = mid % rowlength;
            if (target == matrix[row][col]) {
                return true;
            }
            if (target > matrix[row][col]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == matrix[start/rowlength][start%rowlength]) {
            return true;
        }
        if (target == matrix[end/rowlength][end%rowlength]) {
            return true;
        }
        return false;
    }
};

Similar problems

x

Tags

x