Day 003-Q3 | 二分探索

問題

N個の整数からなるソート済み配列 A と、Q個のクエリがある。各クエリで整数 x が与えられ、「A の中に x 以上の最小の整数が存在するか」を調べ、存在する場合はその値を、存在しない場合は -1 を出力せよ。

入力形式

N Q
A_1 A_2 ... A_N
x_1
...
x_Q

制約

$1 \le N \le 10^5$

$1 \le Q \le 10^5$

$1 \le A_i \le 10^9$（昇順）

$1 \le x_i \le 10^9$

入出力例

入力例 1

6 4
1 3 5 7 9 11
4
7
12
1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

線形探索は O(NQ)=10^10 で TLE。配列がソート済みなので二分探索（O(log N)）を使う。

ヒント2: アプローチ

Python の bisect モジュール。bisect_left(A, x) = x 以上の最初の位置。

ヒント3: 誘導

import bisect
idx = bisect.bisect_left(A, x)
if idx < len(A):
    print(A[idx])
else:
    print(-1)

模範解答 (Python)

import bisect

N, Q = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(Q):
    x = int(input())
    idx = bisect.bisect_left(A, x)
    if idx < len(A):
        print(A[idx])
    else:
        print(-1)

Step-by-Step 解説

1bisect_left の動作
x をソート順を保ったまま挿入する最左位置を返す。A=[1,3,5,7,9,11] で bisect_left(A,4)=2（A[2]=5）。

2境界チェック
idx == len(A) のとき全要素が x 未満 → 存在しない。

3bisect_left vs bisect_right
「x 以上の最小」→ bisect_left。「x より大きい最小」→ bisect_right。

計算量

bisect_left: $O(\log N)$
Q クエリ全体: $O(Q \log N) \approx 1.7 \times 10^6$

よくあるミス

ミス	原因	正しい書き方
`bisect_right` を使う	x 自体を見落とす	`bisect_left`
`idx == len(A)` 処理漏れ	境界条件忘れ	`if idx < len(A)`
手動二分探索でオフバイワン	`lo<=hi` と `lo<hi` の混乱	`bisect` モジュール活用

Day 003-Q3 — 二分探索

問題