[이진 탐색] Leetcode 74. Search a 2D Matrix

https://leetcode.com/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-interview-150

Search a 2D Matrix - LeetCode

https://github.com/fineman999/algorithm_java/issues/5

74. Search a 2D Matrix · Issue #5 · fineman999/algorithm_java

---

서론

이차원 배열에서 이진 탐색을 통해 원하는 target이 있는지 구하는 알고리즘 문제이다.

 

1. 알고리즘 개요

다음 두 가지 속성을 가진 m x n 정수 행렬이 제공된다.

각 행은 감소하지 않는 순서로 정렬된다.
각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 크다.
정수 대상이 주어지면 대상이 행렬에 있으면 true를 반환하고 그렇지 않으면 false를 반환한다.

반드시 O(log(m * n)) 시간 복잡도로 작성해야 한다.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

2. 알고리즘 풀이

주어진 제약 조건 덕분에 이진 탐색으로 풀면 쉽게 구할 수 있을 것 같다. 그럼 이차원 배열을 어떻게 이진 탐색으로 구현할 수 있을까?

이차원 배열을 일차원 배열로

위 그림과 같이 1차원 배열로 생각하면 쉽게 이진 탐색을 구현할 수 있다.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        checkNull(matrix);
        if (matrix.length == 0) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;

        int left = 0;
        int right = row * col - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int midValue = matrix[mid / col][mid % col];

            if (midValue < target) {
                left = mid + 1;
                continue;
            }
            if (midValue > target){
                right = mid - 1;
                continue;
            }
            return true;
        }
        return false;
    }

    private void checkNull(int[][] matrix) {
        if (matrix == null) {
            throw new IllegalArgumentException("matrix must not be null");
        }
    }
}

1. row, col을 구한다.
2. left는 현재 검색 범위의 왼쪽 끝을, right는 오른쪽 끝을 나타낸다. 이때, 이차원 배열을 일렬로 나열하면 총요소의 개수는 row * col이므로 right의 마지막 요소의 인덱스가 된다.
3. 반복문을 실시한다.
   1. mid: 현재 검색범위의 중간 인덱스를 의미한다.
   2. midValue: 이차원 배열을 1차원 배열처럼 변환하여 값을 가져오게 된다.
   3. 이후 midValue와 target을 비교하여 midValue가 작으면 검색 범위를 left를 mid + 1부터 시작하게 하고, midValue가 크면 검색범위를 right를 mid -1로 옮긴다.
   4. 만약 midValue와 target이 같다면 true로 반환한다.
4. 반복이 끝났음에도 target을 찾지 못하면 false를 반환한다.

테스트 결과

leetcode 결과