74. Search a 2D Matrix

문제 설명

m x n 정수형 매트릭스에서 target 값을 찾는 효과적인 알고리즘을 작성하세요. 이 매트릭스는 다음과 같은 특징이 있습니다.

• 각 행 안의 숫자는 왼쪽부터 오른쪽으로 정렬되어 있습니다.
• 각 행의 첫번째 숫자는 이전 행의 마지막 숫자보다 큽니다.

출력 예시

접근 방법

첫번째 시도

매트릭스 두번째 특성을 이용해야겠다... 타겟 값과 각 행의 마지막 숫자 비교를 통해 어느 행에 위치해 있는지 확인 할 수 있다. 그 다음 그 행에서 이분 탐색을 실시해본다.

소스코드

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;
    }
};

돌아보기

2차원 배열이라고 생각하지 않고 matrix[x][y] => a[x * m + y] 로 푸는 방법도 있다.
한번의 while문을 통해 해결가능해짐....