28. Search a 2D Matrix

做题历程：

1. 本题应该在Leetcode曾经做过，本次独立解出， 大概耗时13分钟

本题还是比较简单的，只需要注意细节。

大概步骤：

1. 用Binary Search确定在哪一行
2. 再用Binary Search找最终结果

代码如下：

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() || matrix[0].empty()) {
            return false;
        }
        // search row first
        int start = 0;
        int end = matrix.size() - 1;
        int row = -1;
        while (start + 1 < end) {
            int middle = start + (end - start) / 2;
            if (matrix[middle][0] > target) {
                end = middle - 1;
            }
            else if (matrix[middle][0] == target) {
                return true;
            }
            else {
                start = middle;
            }
        }
        if (matrix[end][0] <= target) {
            row = end;
        }
        else if (matrix[start][0] <= target) {
            row = start;
        }
        else {
            return false;
        }

        start = 0;
        end = matrix[row].size() - 1;
        while (start + 1 < end) {
            int middle = start + (end - start) / 2;
            if (matrix[row][middle] < target) {
                start = middle + 1;
            }
            else if (matrix[row][middle] == target) {
                return true;
            }
            else {
                end = middle - 1;
            }
        }
        if (matrix[row][end] == target || matrix[row][start] == target) {
            return true;
        }
        return false;

    }
};