74. Search a 2D Matrix

Search a 2D Matrix - LeetCode

row, col이 커질수록 큰 값이 들어있는 2차원 배열에서 특정 값이 있는지 탐색하는 문제다.

 

1. 이진 탐색

 

240. Search a 2D Matrix II

동일한 문제지만 2차원 배열 크기가 훨씬 큰 문제에서 사용한 방법을 그대로 사용할 수 있다.

 

2. 이진 탐색 2

from typing import *


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        height, width = len(matrix), len(matrix[0])

        start, end = 0, height * width - 1

        while start <= end:
            mid = start + (end - start) // 2
            cur = matrix[mid // width][mid % width]

            if cur == target:
                return True
            elif cur < target:
                start = mid + 1
            else:
                end = mid - 1
        
        return False

1번 풀이와 별다를 건 없어 보이지만,  row, col 값을 얻을 수 있는 값을 이용해 이진 탐색을 한다.

예를 들어 4 * 5 사이즈의 2차원 배열이라면 start, end를 각각 0, (20 - 1)로 두고 이진 탐색을 하는 셈.

mid 값을 width로 나누면 row의 값을 얻을 수 있고, mid 값을 width로 모듈로 연산하면 col의 값을 얻을 수 있다.

 

건저 갈 게 하나 더 있다면 mid를 구할 때 start + (end - start) // 2로 계산했다는 점인데, python에선 그다지 상관없지만 정수 범위를 제한해서 사용하는 java, c++ 같은 경우에 (start + end) 값이 int 형을 벗어나는 경우가 있기 때문에 저렇게 처리해준다. (값은 계산해보면 같다)