描述

写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。

样例

考虑下列矩阵：

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

挑战

O(log(n) + log(m)) 时间复杂度

思路

由于二维数组是按照严格的升序排列的，所以本题两种解法：

代码

1. 先对矩阵的行进行模板二分法来求确定target处于哪一行，然后再对矩阵的列进行二分法, 确定位置。

public class Solution {
    /**
     * @param 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) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix == null || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length;
        int column = matrix[0].length;

        int start = 0;
        int end = row - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target) {
                return true;
            }
            if (matrix[mid][0] < target) {
                start = mid;
            }
            if (matrix[mid][0] > target) {
                end = mid;
            }
        }
        if (matrix[end][0] <= target) {
            row = end;
        }
        else if (matrix[start][0] <= target) {
            row = start;
        }
        /* 此处应注意,不能把else if 写成if 因为多个if是连续执行的，而数组中元素是升序排列的
         * matrix[end][0], >= matrix[start][0]的, 若不加else可能会出现row = end 却被
         * row = start 覆盖的情形
         */
        else {
            return false;
        }

        start = 0;
        end = column - 1;
        // start,end 前不能加int，因为前面已经定义过start和end了，
        // 变量可以重新赋值，但不能重新定义
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target) {
                return true;
            }
            if (matrix[row][mid] < target) {
                start = mid;
            }
            if (matrix[row][mid] > target) {
                end = mid;
            }
        }
        
        if (matrix[row][end] == target) {
            return true;
        }
        if (matrix[row][start] == target) {
            return true;
        }
        return false;
    }
}

2. Binary Search Once

public class Solution {
    /**
     * @param 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) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
    
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
    
        int row = matrix.length;
        int column = matrix[0].length;
    
        int start = 0, end = row * column - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            // 关键代码
            int number = matrix[mid / column][mid % column];
            if (number == target) {
                return true;
            } else if (number > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    
        return false;
    
    }
}