[LeetCode] Search 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.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Analysis:

We can find the first row whose first element is less than target, and search within that row.

Alternatively, we can take the whole matrix as an array and binary search from start to end.

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int size = matrix.size();
        if(0 == size) return false;
        
        int len = matrix[0].size();
        if(0 == len) return false;
        int start = 0, end = size*len-1;
        
        while(start <= end)
        {
            int mid = start + (end-start)/2;
            int col = mid % len;
            int row = mid / len;
            if(matrix[row][col] > target) end = mid - 1;
            else if(matrix[row][col] < target) start = mid + 1;
            else return true;
        }
        return false;       
    }
};