2차원 배열에서 Binary Search 적용하기

알고리즘을 구현하다보면 2차원 배열에서 분할 탐색을 적용하고 싶을 때가 있다.

특히 알고리즘 문제를 풀 때 이런 경우를 종종 마주치게 되는데, 구현에 익숙하지 않다면 상당히 당황스럽다.

2차원 배열에서 Binary Search 를 적용하기 위해선 몇가지 방법이 있는데, 가장 간단한 방법은 2차원을 1차원으로 축소시켜서 Binary Search 를 적용하는 방법이다.

m개의 행과 n개의 열을 가진 2차원 Matrix 가 있다고 가정해보자.

이를 1차원으로 이해한다면 0~m*n 까지의 Element 가 포함되어 있다고 이해할 수 있다.

그리고 행과 열의 정보는 n 으로 나눈값과 n으로 나눈 나머지를 통해 알 수 있다.

코드를 통해 이해해보자.

public boolean searchMatrix(int[][] matrix, int target) {

if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {

return false;

}

int m = matrix.length;

int n = matrix[0].length;

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) {

start = mid + 1;

} else {

end = mid - 1;

}

}

return false;

}

일반 Binary Search 와 동일한 로직이면서 좌표값만 변경하면서 똑같이 구현한 내용이다.

이진탐색 및 분할정복이 익숙하지 않다면 익혀두고 사용하는 것도 괜찮은 방법이다.