Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
Given target = 3, return true.
Challange
O(log(n) + log(m)) time
1. 两次binary search
先针对每行第一个元素检索，找到可能行；再在可能行内检索。
public class Solution { /* * @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) { //看看这样写行不 if (matrix == null || matrix.length == 0 || matrix[0].length == 0){ return false; } // 对吗 int rows = matrix.length; int cols = matrix[0].length; //find the possible row. int start = 0; int end = rows - 1; int possibleRow = 0; while (start + 1 < end){ int mid = start + (end - start) / 2; if (target < matrix[mid][0]){ end = mid; } else if (target == matrix[mid][0]){ return true; } else { start = mid; } } if (matrix[end][0] > target){ possibleRow = start; } else if (matrix[end][0] == target){ return true; } else { possibleRow = end; } //find in the possible row. start = 0; cols = matrix[possibleRow].length; end = cols - 1; while (start + 1 < end){ int mid = start + (end - start) / 2; if (target < matrix[possibleRow][mid]){ end = mid; } else if (target == matrix[possibleRow][mid]){ return true; } else { start = mid; } } if (matrix[possibleRow][start] == target || matrix[possibleRow][end] == target){ return true; } return false; }}
2.一次binary search
把所有数字连起来看做一个排序一元数组，用/和%提取行列坐标，一次binary search。
public class Solution { /* * @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) { if (matrix == null || matrix.length == 0){ return false; } if (matrix[0] == null || matrix[0].length == 0){ return false; } int rows = matrix.length; int cols = matrix[0].length; int start = 0; int end = rows * cols - 1; while (start + 1 < end){ int mid = start + (end - start) / 2; if (target < matrix[mid / cols][mid % cols]){ end = mid; } else if (target == matrix[mid / cols][mid % cols]){ return true; } else { start = mid; } } if (matrix[start / cols][start % cols] == target || matrix[end / cols][end % cols] == target){ return true; } return false; }}
1.对二元数组的输入判别：
if(matrix == null || matrix.length == 0){ return false;} if(matrix[0] == null || matrix[0].length == 0){ return false;} 2.对二元数组的行列长度提取：（要在判别存在行以后才可以用matrix[0]）
int row = matrix.length;int column = matrix[0].length;