Search a 2D Matrix

Search a 2D Matrix

문제

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

풀이

이진탐색의 라이브러리 bisect를 사용하여 풀이했다.

1. 주어진 배열 matrix를 열 단위로 가져온다.
2. bisect 메서드로 위치를 찾는다.
   start_idx: bisect_left
   end_idx: bisect_right
3. start_idx + 1 <= end_idx의 결과라면 return True
   == 가 아닌 <= 인 이유는 [[1, 1]] 에서 1을 찾을때 start_idx는 0, end_idx는 2가 되기 때문이다.

수도 코드

for matrix의 열을 하나씩 가져온다:
	start_idx = bisect_left 계산
    end_idx = bisect_right 계산
    if start_idx + 1 <= end_idx return True
return False

Solution(Runtime: 28ms)

from bisect import bisect_left, bisect_right

class Solution(object):
    def searchMatrix(self, matrix, target):
        for row in matrix:
            start_idx = bisect_left(row, target)
            end_idx = bisect_right(row, target)
            if start_idx + 1 <= end_idx:
                return True
          
        return False

다른 사람들은 row, col 변수를 두고 위치를 찾도록 풀이했다.

• 현재 배열의 값 > target: col -= 1
• 현재 배열의 값 < target: row += 1
• else 같으므로: True