74. Search a 2D Matrix

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

main idea: 2D -> 1D, because it's ordered, we can use binary search

/*
    use binary search
    
    time complexity: O(log(m*n)) space complexity: O(1)
*/
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        
        int m = matrix.length; // 2d -> look as a 1-d array, matrix[m][n] looks like a[m*n]
        int n = matrix[0].length;
        
        int left = 0;
        int right = m*n - 1;
        
        while (left <= right) {
            int mid = left + (right - left)/2;
            int matrixVal = matrix[mid/n][mid%n]; // 1d index
            
            if (matrixVal == target) {
                return true;
            }
            
            if (matrixVal > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

my idea, also 100%...

time: O(m*logn)

space: O(1)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // target == first, return true, target > first do bs
        // 12
        // result == row.length
        // i++
        int m = matrix.length;
        int n = matrix[0].length;
        int row = 0;
        while (row < m) {
            int col = 0;
            int first = matrix[row][col];
            if (target == first) return true;
            if (target < first) {
                return false;
            }
            
            int left = 0;
            int right = n - 1;
            while (left <= right) {
                int mid = (left + right) >> 1;
                if (matrix[row][mid] == target) {
                    return true;
                } else if (matrix[row][mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            row++;
        }
        return false;
        
    }
    
}