74. Search a 2D Matrix - Medium

前往題目

想法

• 之前做過，題目要求O(log(m * n))以為不能疊代整個矩陣，於是先用binary search尋找target可能在哪一行，然後再搜尋特定那一行
• 看了之前我的submission才發現其實可以，因為都用binary search所以每行都檢查的話就符合題目要求的time complexity

思路

1. 疊代每行
2. 在每行binary search target

Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        final int M = matrix.length;
        final int N = matrix[0].length;

        for (int row = 0; row < M; ++row) {
            int l = 0, r = N - 1;

            while (l <= r) {
                int mid = l + (r - l) / 2;

                if (matrix[row][mid] == target) {
                    return true;
                } else if (matrix[row][mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }

        return false;
    }
}