Search a 2D Matrix II

Problem

Search a 2D Matrix II

Intuition

1. My first solution is to use Binary Search to reach the answer, because every row or col in the matrix is sorted.
2. However, my first method isn’t efficient and it takes lots of time in searching the target in some arrays not included the target element. So, the better way is to start at the point(row - 1, 0). The reason is that starting from left-bottom can control our directions. If the value of current location is bigger than target, go to the up. If smaller, go to the right.

Code

// binary search
class Solution {
    private boolean binarySearch(int[] nums, int target){
        int L = 0, R = nums.length - 1;
        if(nums[L] > target || nums[R] < target) return false;
        while(L <= R){
            int mid = L + (R - L) / 2;
            if(nums[mid] >= target){
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return nums[L] == target;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0) return false;
        for(int i = 0; i < matrix.length; i ++){
            if(binarySearch(matrix[i], target)){
                return true;
            }
        }
        return false;
    }
}

// second edition
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int N = matrix.length;
        if(N == 0) return false;
        int M = matrix[0].length;
        int row = N - 1, col = 0;
        while(row >= 0 && col < M){
            if(matrix[row][col] == target) {
                return true;
            }
            if(matrix[row][col] < target){
                col ++;
            } else {
                row -- ;
            }
        }
        return false;
    }
}