// Use one binary search by converting 2D to 1D
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;
        }

        // Transform 2D matrix to 1D array and indexing through 0 to row * col - 1;
        int start = 0;
        int end = row * col - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int x = mid / col; // row number is equal to mid / col;
            int y = mid % col; // col number is equal to mid % col;
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                start = mid;
            } else {
                end = mid;
            }
            if (matrix[start/col][start%col] == target) {
                return true;
            }
            if (matrix[end/col][end%col] == target) {
                return true;
            }
        }
        return false;
    }
};