题目

搜索二维矩阵中是否包含特定元素，二维矩阵具有以下特性：

• 每行中的整数从左到右是排序的。
• 每行的第一个数大于上一行的最后一个整数

要求时间复杂度为O(log(n) + log(m)) ，原题链接：http://www.lintcode.com/zh-cn/problem/search-a-2d-matrix/

分析

既然二维矩阵是有序的，毫无疑问应当使用二分查找，先确定是否存在一行，能够满足line[0]>=target && line[line.length - 1] <= target，然后再在这一行中进行二分搜索。

代码

 boolean findCol(int[] row, int target, int start, int end){
        if(end == start+1){
            if(row[start] == target) return true;
            if(row[end] == target) return true;
            return false;
        } 
        int mid = (start+end)/2;
        if(row[mid] == target) return true;
        else if(row[mid] > target) return findCol(row, target, start, mid);
        else return findCol(row, target, mid+1, end);
    }
    
    int findRow(int[][] matrix, int target, int start, int end){
        if(start > end) return -1;
        int mid = (start+end)/2;
        int[] line = matrix[mid];
        if(line[0]<=target && line[line.length-1] >=target){
            return mid;
        }
        if(start == end){
            return -1;   
        }
        if(line[0]>target) return findRow(matrix, target, start, mid);
        if(line[line.length-1]<target) return findRow(matrix, target, mid+1, end);
        return -1;
    }
    /*
     * @param matrix: matrix, a list of lists of integers
     * @param target: An integer
     * @return: a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // 有可能找不到包含target的行
        int rowIndex = findRow(matrix, target, 0, matrix.length-1);
        if(rowIndex<0) return false;
        int[] line = matrix[rowIndex];
        return findCol(line, target, 0, line.length-1);
    }