병렬 이분 탐색 (Parallel Binary Search)

정의

병렬 이분 탐색 (Parallel Binary Search, PBS) 은 Q 개의 쿼리를 각각 독립적으로 이분탐색하지 않고, 모든 쿼리의 이분탐색을 라운드별로 동시에 진행하는 오프라인 테크닉. 한 라운드에서 모든 쿼리가 같은 자료구조를 공유하므로 한 번의 스윕으로 Q 개 쿼리를 동시에 평가.

문제 상황과 동기

Q 개 쿼리 각각에 대해 T(log N) 시간의 check 함수로 이분탐색을 하면 O(Q log N * T). PBS 로 자료구조 갱신 비용을 라운드당 O(N) 으로 amortize 하여 총 O((N + Q) log N). check 함수가 자료구조와 자연스럽게 맞물릴 때 효과적.

핵심 통찰: 이분탐색의 각 mid 값은 정렬된 순서로 일괄 처리 가능. 모든 쿼리의 mid 를 모아 한 번의 sweep 으로 K 개 쿼리 동시 평가.

시각화

핵심 아이디어

invariant: 각 쿼리 i에 대해 lo[i] ≤ answer_idx[i] ≤ hi[i]. 모든 쿼리가 lo == hi 가 될 때까지 반복.

for round = 1..logN:
    for each query i with lo[i] < hi[i]:
        mid[i] = (lo[i] + hi[i]) / 2
        bucket[mid[i]].push(i)

    reset data structure
    for value v in sorted order:
        add v to DS
        for each query i in bucket[v.position]:
            if check(i) passes:
                hi[i] = mid[i] - 1, record answer
            else:
                lo[i] = mid[i] + 1

amortized: 모든 쿼리가 O(log N) 라운드 동안 각각 한 번씩만 체크. DS 갱신은 라운드당 O(N).

알고리즘

PBS(sorted_values[], Q, k[]):
    lo[0..Q-1] = 0
    hi[0..Q-1] = N-1

    while some lo[i] <= hi[i]:
        buckets[][] = empty
        for i in 0..Q-1:
            if lo[i] <= hi[i]:
                mid = (lo[i] + hi[i]) / 2
                buckets[mid].append(i)

        seen = 0
        for pos in 0..N-1:
            seen++
            for idx in buckets[pos]:
                if seen >= k[idx]:
                    hi[idx] = pos - 1
                    ans[idx] = sorted_values[pos]
                else:
                    lo[idx] = pos + 1

    return ans[]

구현

// PBS: Q queries, each asks k_i-th smallest in the array
// O((N + Q) log N)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
​
  int n, q; cin >> n >> q;
  vector<ll> a(n);
  for (auto& v : a) cin >> v;
  vector<ll> sorted = a;
  sort(sorted.begin(), sorted.end());
​
  vector<int> k(q);
  for (int i = 0; i < q; i++) cin >> k[i];
​
  // PBS: lo, hi are sorted array indices (0-based)
  vector<int> lo(q, 0), hi(q, n - 1);
  vector<ll> ans(q);
​
  while (true) {
      // 1. Group queries by mid value
      vector<vector<int>> by_mid(n);
      bool done = true;
      for (int i = 0; i < q; i++) {
          if (lo[i] <= hi[i]) {
              done = false;
              int mid = (lo[i] + hi[i]) / 2;
              by_mid[mid].push_back(i);
          }
      }
      if (done) break;
​
      // 2. Sweep sorted values in order, check queries at their mid
      int seen = 0;
      for (int m = 0; m < n; m++) {
          seen++;
          for (int idx : by_mid[m]) {
              if (seen >= k[idx]) {
                  hi[idx] = m - 1;
                  ans[idx] = sorted[m];
              } else {
                  lo[idx] = m + 1;
              }
          }
      }
  }
​
  for (auto& v : ans) cout << v << "\n";
  return 0;
}

# PBS: Parallel binary search, Q queries simultaneously
import sys
input = sys.stdin.readline
​
def pbs(arr, queries):
  arr.sort()
  n = len(arr)
  q = len(queries)
  lo, hi = [0] * q, [n - 1] * q
  ans = [0] * q
​
  while True:
      by_mid = [[] for _ in range(n)]
      done = True
      for i in range(q):
          if lo[i] <= hi[i]:
              done = False
              mid = (lo[i] + hi[i]) // 2
              by_mid[mid].append(i)
      if done:
          break
​
      seen = 0
      for m in range(n):
          seen += 1
          for idx in by_mid[m]:
              if seen >= queries[idx]:
                  hi[idx] = m - 1
                  ans[idx] = arr[m]
              else:
                  lo[idx] = m + 1
​
  return ans
​
n, q = map(int, input().split())
a = list(map(int, input().split()))
queries = [int(input()) for _ in range(q)]
results = pbs(a, queries)
print("\n".join(map(str, results)))

7 3
10 5 8 1 7 3 15
3
5
1

5
10
1

복잡도

변형 / 활용

• K-th number in range: Fenwick tree 로 구간 내 k번째 수 검색. 각 라운드마다 values 를 sorted order 로 삽입하며 체크.
• Parametric search 병렬화: 여러 쿼리가 각자의 threshold 를 만족하는 최소값을 찾을 때 사용.
• Mo’s + PBS: Mo’s 알고리즘과 결합하여 O(N sqrt N log N) 해결 (offline dynamic queries).

함정

1. 자료구조 초기화 비용

각 라운드마다 DS 를 O(N) 에 초기화해야 함. O(N log N) 이면 라운드당 log factor 가 붙어 PBS 이점이 사라짐. Fenwick tree (O(N) build via prefix sum) 사용 권장.

2. 단조성 필요

check(i) 가 단조적이어야 함: mid 값이 증가하면 check(i) 결과도 monotonic. 이 조건이 깨지면 이분탐색 자체가 성립하지 않음.

3. 오프라인 한정

모든 쿼리를 미리 알고 있어야 함. 온라인 쿼리 (실시간 삽입) 에는 각각 독립 이분탐색 필요.

BOJ 연습 문제

참고

• 이분 탐색
• 매개 변수 탐색
• Mo’s 알고리즘