Binary search로 삽입 위치 찾기 - 그림으로 쉽게 이해하기

Binary search의 기본 개념

Binary search의 원리

Binary search는 정렬된 리스트에 있는 숫자들 중 특정 target을 찾는 문제이다. 정렬되어 있다는 전제가 깔려있기 때문에, 영역을 절반씩 쪼개면서 탐색하면 O(logN) 시간복잡도로 풀 수 있다. 영역을 절반씩 쪼갠다는 것은 무슨 의미일까? 전체 리스트의 중간에 있는 숫자만 확인하면, 리스트의 앞 절반과 뒤 절반 중 target이 위치한 곳이 어딘지 예상할 수 있다. 그렇다면 두 영역 중 확인할 필요가 없는 영역은 버리고, 남은 절반 안에서 target을 찾으면 된다. 똑같은 동작을 반복한다면, 매번 탐색 영역이 절반으로 줄게 된다. 리스트의 모든 숫자를 하나씩 확인하는 것에 비해 훨씬 효율적이다.

용어 정의

설명의 편의를 위해 다음 용어들을 정의하고 넘어가자.

• L: 정렬된 리스트
• t: 찾고자 하는 값
• s: 탐색하고자 하는 영역의 시작 인덱스
• e: 탐색하고자 하는 영역의 끝 인덱스
• m: 탐색하고자 하는 영역의 중간 인덱스 m = (s + e) / 2

이진 탐색 python 코드 예시

t가 L에 존재하면 그 위치를 반환하고, 존재하지 않으면 -1을 반환하도록 하는 binary search 코드는 다음과 같이 짜면 된다.

def binary_search(L: list, s: int, e: int, t: int) -> int:
  while s <= e:
    m = int((s + e) / 2)
    if L[m] > t:
      e = m - 1
    elif L[m] < t:
      s = m + 1
    else:
      return m
  return -1

영역을 절반씩 좁혀가면서, L[m]과 t를 비교하는 루프를 돈다. 더이상 영역을 줄일 수 없는 상태에서 마지막 남은 숫자가 t가 아니라면, 루프를 벗어나서 -1을 반환한다.

삽입 위치 탐색 방법

삽입 위치 탐색 문제란?

t를 찾지 못했을 때 -1을 반환하는 것이 아니라, 정렬된 L에서 t가 삽입될 인덱스를 반환하려면 어떻게 코딩을 해야 할까? LeetCode 사이트의 Search Insert Position 문제를 먼저 풀어보길 권장한다.

Python 코드 정답 스포일러

def binary_search(L: list, s: int, e: int, t: int) -> int:
  while s <= e:
    m = int((s + e) / 2)
    if L[m] > t:
      e = m - 1
    elif L[m] < t:
      s = m + 1
    else:
      return m
  return s

맨 마지막 return 부분만 바뀌었다. 이렇게 외우고 사용해도 되지만, 시간이 흐르면 잊어버리기 일쑤다. 위 코드가 정답인 이유가 무엇일까? 차근차근 살펴보자.

정답 해설: edge case 시각화

루프가 진행되면서 영역이 점점 좁아지는 것에 착안하여, edge case를 중심으로 분석해보자. L 안에 t가 존재하는 경우에는 바로 해당 위치를 반환하면 된다. 따라서, 고려 대상에서 제외한다. 존재하지 않는 t의 삽입 위치를 찾는 것에만 집중하자. 가장 먼저 생각해볼 수 있는 것은 s == e인 상태이다. 시각적인 이해를 위해 다음과 같이 특수한 이진 트리를 정의해보자.

이 트리에서 노드는 루프 중 특정 스텝에서 확인 중인 영역의 상태를 의미한다. 노드에서 왼쪽으로 뻗어나가는 것은 t가 m보다 왼쪽에 있음을 의미하며, 오른쪽으로 뻗어나가는 것은 그 반대를 의미한다. 위 그림에서는 왼쪽, 오른쪽 모두 e < s인 상태로 가기 때문에, 아래의 자식 노드들은 모두 코드의 while 부분을 빠져나와 마지막 return s를 호출하는 부분으로 이어진다.

마지막까지 t를 찾지 못했다는 것은 무슨 의미일까? 위 그림에서 왼쪽으로 이동했다는 것은 t가 s보다 왼쪽에 위치한다는 의미이다. 반대로, 오른쪽으로 이동했다는 것은 t가 e보다는 오른쪽에 위치한다는 의미이다. 다시 말해서, t는 e와 s 사이에 위치하는 것이다. 인덱스로 따지면 s 부분이 곧 t가 삽입될 위치라는 것을 알아차릴 수 있다.

그렇다면, 루프를 돌다가 다음과 같이 한 칸 차이, 즉, s == e - 1인 상태가 된 경우에는 어떻게 될까?

오른쪽으로 가는 경우는 이미 s == e인 경우에서 살펴봤으므로 더이상 확인할 필요가 없다. 왼쪽으로 가는 경우도 역시 e < s가 되면서 루프를 빠져나오게 된다. 앞서 언급했듯이 t가 e와 s 사이에 있으므로, s 위치에 t를 삽입하면 된다. 따라서, return s는 t가 삽입될 위치를 반환하는 것과 같은 의미가 된다.

마지막으로 두 칸 차이, 즉, s == e - 2 상태인 그림 하나를 더 살펴보자.

감이 오는가? 더 확인할 필요가 없다. return s의 의미는 t가 삽입될 위치를 반환하는 것이라는 결론을 내릴 수 있다.

결론: 어떻게 코드를 작성하면 될까?

찾기 문제와 삽입 문제 모두 동일한 binary search 로직을 사용하지만, 반환 값만 서로 다르다는 것을 기억하자.

• 찾기 문제는 t가 L 안에 없는 경우 return -1을 해준다.
• 삽입 문제는 t가 L 안에 없는 경우 return s를 해준다.