74. Search a 2D Matrix

问题
Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

二分搜索，以整个数组尺寸作为搜索范围。
每次搜索中间值，如等于target则返回。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        int right = (matrix.length * matrix[0].length) - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int row = mid / matrix[0].length;
            int col = mid % matrix[0].length;
            if(matrix[row][col] == target){
                return true;
            }
            else if(matrix[row][col] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return false;
    }
}

双指针，先搜索到合适的行。
再搜索到合适的列。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = 0;
        
        while(i < matrix.length){
            if(matrix[i][0] == target){
                return true;
            }
            else if(matrix[i][0] < target){
                i++;
            }
            else{
                break;
            }
        }
        if( i == 0 ){
            return false;
        }
        i--;
        while(j < matrix[0].length){
            if(matrix[i][j] == target){
                return true;
            }
            j++;
        }
        return false;
    }
}