#이진탐색 #행렬이라면?

Q. 각 행과 열이 오름차순으로 정렬된 상태인 M*N 행렬이 주어졌을 때, 특정한 원소를 찾는 메서드를 구하여라. 

- 각 행과 열이 정렬된 상태이기 때문에, 선형탐색보다는 이진 탐색을 하는 것이 더 바람직하다. 다만, 이진 탐색을 어떤 범위로 할 것인지가 중요하다.

- 만약, 1) 행마다의 이진 탐색을 적용하는 각 행을 탐색하는 데에는 O(logN)의 시간이 걸리며, 총 M개의 행의 경우 O(M log N)의 시간이 걸린다.  

- 그렇다면 다른 방법은 없을까? 먼저 행렬을 살펴보자. 행렬에 있는 값들과 특정값을 비교할 때, '정렬된' 행렬에서 어떤 공통된 규칙이 있을까?

(브레인스토밍 단계에서)

i) 어떤 열의 시작점 원소값이 x보다 크다면 x는 그 열 왼쪽에 존재한다.

ii) 어떤 열의 마지막 원소값이 x보다 작다면, x는 해당 열 오른쪽에 있다. 

iii) 어떤 행의 시작점 원소값이 x보다 크다면, x는 해당 행 위에 있다.

iv) 어떤 행의 마지막 원소값이 x보다 작다면, x는 해당 행 아래에 있다.

이진탐색 문제를 적용하기 위해서 생각을 확장해 나가면, 위의 그림의 아이디어를 떠올릴 수 있다.

즉, 각각 네모난 영역에서의 왼쪽 상단의 값과 오른쪽 하단의 값은 각각 네모난 영역에서의 최솟값과 최대값을 뜻한다. 

def sorted_matrix_search(mat, item):

  if len(mat) == 0: #행의 크기가 0이면 찾고자 하는 값이 없다. 

    return None
#범위를 탐색하기 위해서, 행-열로 표시
  return sorted_matrix_search_bounds(mat, item, 0, len(mat), 0, len(mat[0])) 
  
  def sorted_matrix_search_bounds(mat, item, x1, x2, y1, y2):

  if x1 == x2 or y1 == y2:

    return None

  row, col = (x1 + x2)//2, (y1 + y2)//2 #각 행과 열에 대한 중간값으로 설정
  middle = mat[row][col] #중간값

  if middle == item:
    return (row, col)

  if middle > item: #연두색 구획 안에 찾고자 하는 값이 있을 수 있다. 
    #그 구획을 다시 나눈다 #row to row+1 은 해당 행렬에서 탐색
    
    found = sorted_matrix_search_bounds(mat, item, x1, row, y1, col) or sorted_matrix_search_bounds(mat, item, x1, row, col, col+1,) or sorted_matrix_search_bounds(mat, item, row, row+1, y1, col )
           

    if found:
        return found

  else: #middle보다 찾고자 하는 값이 더 크므로
	#진초록 구획에서 찾는 방법
    found = sorted_matrix_search_bounds(mat, item, row+1, x2, col+1, y2) or sorted_matrix_search_bounds(mat, item, row+1, x2, col, col+1) or sorted_matrix_search_bounds(mat, item, row, row+1, col+1, y2)
            
            

    if found:

      return found

  return sorted_matrix_search_bounds(mat, item, row+1, x2, y1, col) or sorted_matrix_search_bounds(mat, item,  x1, row, col+1, y2)
         

 

if found 구문에서, found에 어떤 자료형이 들어 있으면, None 이 아니므로 그 값을 반환하게 된다. 

found = 여러 값들의 후보로 'or'를 사용해 표기할 수 있다는 점