74. Search a 2D Matrix

問題の説明

mxn整数行列でターゲット値を探す有効なアルゴリズム.この行列には、次のような特徴があります.
各行

の数字は左から右に並んでいます.

各行

の最初の数字は、前の行の最後の数字より大きい.

出力例

方法

初めての試み

マトリクスの2番目の特性を利用するには...ターゲット値と各行の最後の数値を比較することで、どの行にあるかを決定できます.そしてその一行でその人の探索を行う.

ソースコード

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_floor=0;
        int row = matrix.size();
        int column = matrix[0].size();
        for(int i=0; i<row; i++){
            if(matrix[i][column-1] < target) row_floor++;
            else break;
        }
        if(row_floor >= row) return false;

        int start=0;
        int end=column-1;
        int mid = (start + end)/2;
        while(start <= end){
            mid = (start + end)/2;
            cout << mid<<endl;
            if(matrix[row_floor][mid] > target) end = mid-1;
            else if(matrix[row_floor][mid] < target) start= mid+1;
            else return true;
        }
        
        return false;
    }
};

レビュー

二次元配列とは考えず,行列[x][y]=>a[x*m+y]で解く方法もある.
1回のwhile文で解決できます...