[LeetCode]Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 m*n 2D Matrix에서 원하는 target 값이 있는지 찾는 문제입니다.

 

처음 시도한 답안

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for m in matrix:
            left = 0
            right = len(m)-1

            while left <= right:
                mid = (left+right) // 2

                if m[mid] == target:
                    return True
                
                if m[mid] > target:
                    right -= 1
                else: 
                    left +=1

        return False

접근 방법

1. matrix의 행을 순회하면서 이분 탐색을 진행합니다.
   1. 행에서 숫자의 연속성을 확인할 수 없으므로, 행마다 이분 탐색을 반복하여 target값을 찾으면 됩니다.
2. 기본적인 이분 탐색을 진행합니다.
   1. left와 right값을 설정하고 중간값인 mid를 설정합니다.
   2. 만약 target을 찾았다면 True를 리턴합니다.
   3. mid값이 target보다 크다면 right를 -1하여 왼쪽을 탐색합니다.
   4. mid값이 target보다 작다면 left를 +1하여 오른쪽을 탐색합니다.
3. 행을 모두 반복해도 target을 찾지 못했다면 존재하지 않는 것이므로 False를 리턴합니다.

행의 수만큼 개별적으로 이분 탐색을 진행하면 손쉽게 풀이할 수 있습니다.

 

이전에 풀이한 문제와 굉장이 유사합니다. 행에서 연속된 숫자가 아니란 점이 다른 점입니다. 

https://leffept.tistory.com/499

[LeetCode]Search a 2D Matrix