Search a 2D Matrix

https://leetcode.com/problems/search-a-2d-matrix/description/

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.

Thoughts

把问题依然当成是一维的bin search, 直到必须读取matrix数据时才把一维index转化成二维坐标。

Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = m == 0 ? 0 : matrix[0].length;
        int start = 0, end = m * n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / n][mid % n] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (n == 0 || start == m * n || matrix[start / n][start % n] != target) {
            return false;
        } else {
            return true;
        }
    }
}

Analysis

O(lgmn)时间复杂度，O(1)空间复杂度。

在调用维度转换时误把n写成了m.