74. Search a 2D Matrix - cocoder39/coco39_LC GitHub Wiki

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        if (row == 0) { // matrix is empty
            return false; 
        } 
        int col = matrix[0].size();
        if (col == 0) {
            return false;
        }
        
        int start = 0;
        int end = row * col - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            int i = mid / col;
            int j = mid % col;
            if(matrix[i][j] > target){
                end = mid;
            } else if(matrix[i][j] < target){
                start = mid;
            } else{ //matrix[i][j] == target
                return true;
            }
        }
        
        if (matrix[start / col][start % col] == target || matrix[end / col][end % col] == target) {
            return true;
        }
        return false;
    }

public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int low_row = 0;
        int high_row = matrix.length - 1;
        while (high_row - 1 > low_row) {
            int mid = low_row + (high_row - low_row) / 2;
            if (matrix[mid][0] > target) {
                high_row = mid;
            } else {
                low_row = mid;
            }
        }
        int row = matrix[high_row][0] <= target ? high_row : low_row;
        
        int low_col = 0;
        int high_col = matrix[0].length - 1;
        while (high_col - low_col > 1) {
            int mid = low_col + (high_col - low_col) / 2;
            if (matrix[row][mid] > target) {
                high_col = mid;
            } else {
                low_col = mid;
            }
        }
        return matrix[row][high_col] == target || matrix[row][low_col] == target;
    }