2차원 배열에서 이분 탐색 사용하기

2차원 배열에서 이분탐색을 적용하고 싶었다.

https://leetcode.com/problems/search-a-2d-matrix/?envType=study-plan&id=algorithm-ii

Search a 2D Matrix - LeetCode

가장 간단하게는, 2차원을 1차원으로 축소시켜서 이분탐색을 적용한다.

m*n의 2차원 배열이 있다고 한다면,

1차원적으로 보면, 0....m*n까지의 원소가 있다고 볼 수 있다.

 

2차원 배열이니까, 행과 열에 대한 정보를 알아야 한다.

행에 대한 정보는 n으로 나눠서, 열에 대한 정보는 n으로 나머지 연산을 한다.

 

밑의 그림을 통해서 살펴보자.

 

1234

5678

9101112 로 오름차순 정렬된 2차원 배열에 대해서, start를 0으로 잡고, end를 행 * 열 -1 로 잡는다.

m = 3 , n = 4

start = 0, end = 11. 이제 mid값은 start와 end를 더해서 2로 나눈 5가 되고, 

2차원 배열을 1차원으로 길게 늘어놨을떄, 5번쨰 인덱스에 있는 값이 2차원에서 어디 있는지 살펴보자.

 

그림에서 보다시피 5번쨰 인덱스 6은 1행, 1열에 있다.

 

mid = 5, n = 4

mid를 n으로 나눈 값은 1이고 이는 행에 대한 정보이다.

mid를 n으로 나머지 연산을 한 값은 1이고, 이는 열에 대한 정보이다.

 

즉, 1행 1열에 6이 있음을 확인할 수 있다.

 

이를 통해 위의 문제를 해결하면 다음과 같다.

 

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int start = 0;
        int end = m*n - 1;

        while(start <= end){
            int mid = (start + end) / 2;
            int midX = mid / n;
            int midY = mid % n;
            if(matrix[midX][midY] == target){
                return true;
            }
            if(matrix[midX][midY] > target){
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }
        return false;