Leetcode 74. Search a 2D Matrix

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.

For example,

Consider the following matrix:

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

Given target = 3, return true.

---

解题思路：

做两次binary search, 先找在哪一行，即比较第一列，last number <= target.

找到那一行了，再用binary search找哪一列. 时间复杂度还是O(logn)

---

Java code:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //binary search twice, first use first column to find in which row 
        //then go to the row, find in which column
        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;
        
        //find the row index, the last number <= target
        int start = 0;
        int end = row - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(matrix[mid][0] == target) {
                return true;
            }else if(matrix[mid][0] < target) {
                start = mid;
            }else {
                end = mid;
            }
        }
        if (matrix[end][0] <= target) {
            row = end;
        } else if (matrix[start][0] <= target) {
            row = start;
        } else {
            return false;
        }
        
        //find the column index, the number equal to target
        start = 0;
        end = column - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(matrix[row][mid] == target) {
                return true;
            }else if(matrix[row][mid] < target) {
                start = mid;
            }else {
                end = mid;
            }
        }
        if(matrix[row][start] == target){
            return true;
        }else if (matrix[row][end] == target) {
            return true;
        }else {
            return false;
        }
    }
}

---

Reference:

1. http://www.jiuzhang.com/solutions/search-a-2d-matrix/