Lintcode: Search a 2D Matrix

Write an efficient algorithm that searches for a value in anm 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.

Have you met this question in a real interview? 

Yes

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

Tags Expand 

Binary Search Matrix

Way 1
We can transit the two dimensional indexes into one dimensional index then use binary search
Time: O(log(rows * cols))
Space: O(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
        int row = matrix.size();
        if(row == 0) return false;
        int col = matrix[0].size();
        if(col == 0) return false;
        
        int start = 0;
        int end = row * col - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            int i = mid / col;
            int j = mid % col;
            if(matrix[i][j] == target) return true;
            if(matrix[i][j] > target) end = mid - 1;
            if(matrix[i][j] < target) start = mid + 1;
        }
        return false;
    }
};

way 2
Linear search the row and then linear search the col
Time: O(row + col)
space: O(1)

way 3
Use binary search to get the row then binary search the col.
Optimized way 2
Time: O(log(row)+log(col))
Space: O(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
        int row = matrix.size();
        if(row == 0) return false;
        int col = matrix[0].size();
        if(col == 0) return false;
        //binary search row
        int start = 0;
        int end = row - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(matrix[mid][col - 1] == target) return true;
            if(matrix[mid][col - 1] > target) end = mid - 1;
            if(matrix[mid][col - 1] < target) start = mid + 1;
        }
        if(start == row) return false;
        int targetRow = start;
        //binary search col
        start = 0;
        end = col - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(matrix[targetRow][mid] == target) return true;
            if(matrix[targetRow][mid] > target) end = mid - 1;
            if(matrix[targetRow][mid] < target) start = mid + 1;
        }
        return false;
    }
};

Reference:
http://www.cnblogs.com/springfor/p/3857959.html //way 1 & way 3
http://siddontang.gitbooks.io/leetcode-solution/content/array/search_a_2d_matrix.html //way2


Lintcode second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

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