PostsSeriesLabsAlgo

탐색

왼쪽 끝·오른쪽 끝 찾기

같은 값이 여러 개일 때

번호표가 1 2 2 2 3 5 로 줄을 섰습니다. 카드와 카드 사이의 틈에 번호가 붙어 있습니다. 번호표 2 가 몇 장인지 세지 않고 알아내 보세요.

칸 사이에 틈 번호가 붙어 있습니다. 목표: 2 가 몇 장인지 세지 말고 틈 두 개로 알아내기. 2 묶음이 시작되는 틈을 누르세요

122235

지금 찾는 값 2 · 시작 틈(L)

틈을 누른 횟수 0

2 는 끝 틈 4 − 시작 틈 1 = 3장이었습니다. 줄에 없는 4 는 5 − 5 = 0장, 두 틈이 한 자리에 겹쳤습니다.

시작 틈 bisect_left · 끝 틈 bisect_right개수 = 끝 틈 − 시작 틈. 없는 값이면 두 틈이 같아 0장.

둘 다 이분 탐색입니다. 값 하나를 찾는 대신 경계 틈을 찾습니다. 그래서 같은 값이 얼마나 많아도 틈 두 개면 끝납니다.

하나씩 세기1,000,000번
틈 두 개 찾기40번
100만 장 중 같은 값이 몇 장인지 알아낼 때 최악의 횟수.

정렬돼 있고 같은 값이 한 덩어리여야 한다

  • 정렬돼 있다 — 가운데를 보고 한쪽을 통째로 버리려면 필요하다. 이분 탐색과 같다
  • 한 덩어리 — 정렬되면 같은 값은 자연히 붙는다. 그래서 두 틈 사이가 곧 개수다
  • 틈은 늘 생긴다— 값이 없어도 “들어갈 자리”가 있다. 4 가 그랬다

왼쪽 끝과 오른쪽 끝은 비교 한 줄만 다르다

  • 찾았다고 멈추지 않는다 — 같은 값이 더 있을 수 있어서 경계가 나올 때까지 좁힌다
  • lo hi — 칸이 아니라 틈 번호다. hi 는 len(arr) 에서 시작한다
  • hi = mid — mid 칸이 경계 바로 뒤일 수 있어 mid - 1 이 아니라 mid 에 둔다

찾는 값과 코드를 골라 다음을 눌러 보세요. 중간에 한 번 물어봅니다.

오른쪽 코드는 비교 한 줄만 < 에서 <= 로 바뀐 것입니다.

다음을 눌러 한 줄씩 넘겨 보세요

lo = 0 hi = 6

bisect_left.py
  1. 1def bisect_left(arr, x):
  2. 2 lo, hi = 0, len(arr)
  3. 3 while lo < hi:
  4. 4 mid = (lo + hi) // 2
  5. 5 if arr[mid] < x:
  6. 6 lo = mid + 1
  7. 7 else:
  8. 8 hi = mid
  9. 9 return lo
0 / 15

1 2 2 2 3 5 에서 2 를 찾을 때, bisect_right 는 몇 번 틈을 돌려줄까요?

경계에서 틀리는 자리

  • 정렬 안 된 줄에 쓰면 — 에러 없이 틀린다. [1, 2, 5, 3] 에서 3 의 자리를 물으면 2 가 나오는데 그 칸은 5 다
  • 없는 값도 답이 나온다 — -1 이 아니라 들어갈 자리다. 있는지는 i < len(a) and a[i] == x 로 확인한다. i 가 6 이면 a[6] 은 IndexError
  • hi = mid 를 hi = mid - 1 로 쓰면 — 같은 줄에서 2 의 시작 틈이 1 이 아니라 0 이, 4 의 자리가 5 가 아니라 4 가 나온다
  • lo = mid + 1 에서 + 1 을 빼면 — [1, 2] 에서 2 를 찾을 때 끝나지 않는다

문제에서 이 말이 보이면

같은 값이 여러 개개수를 세야 한다x 이상이 처음 나오는 자리

파이썬에는 이미 있습니다. from bisect import bisect_left, bisect_right 로 불러 씁니다. 개수는 bisect_right(a, x) - bisect_left(a, x) 입니다.

다음 장에서는 정렬된 줄이 없어도 쓰는 이분 탐색, 답을 이분 탐색하는 방법을 봅니다.