搜索二维矩阵

题目

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

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

要求时间复杂度为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);
    }

Show Comments

Get the latest posts delivered right to your inbox.