クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「3-1 lower_bound」(p.128)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-1 lower_bound」(p.128)
のコードをPythonで書き直したものとなっています。

入力


n\,k\\a_0\,…\,a_{n-1}

入力例



5 3
2 3 3 5 6


蟻本のコード

# 入力
n, k = map(int,input().split())
a = list(map(int,input().split()))

# 解の存在範囲を初期化
lb = -1
ub = n

# 解の存在範囲が1より大きい間、繰り返す
while ub - lb > 1:
    mid = (lb + ub) // 2
    if a[mid] >= k:
        # midが条件を満たせば、解の存在範囲は(lb, mid]
        ub = mid
    else:
        # midが条件を満たさなければ、解の存在範囲は(mid, ub]
        lb = mid

# この時点で、lb + 1 = ubとなっている
print(ub)

bisect_leftを使ったコード


Pythonにはbisect_leftという関数として、bisectモジュールに含まれています。

from bisect import bisect_left

# 入力
n, k = map(int,input().split())
a = list(map(int,input().split()))

i = bisect_left(a, k)
print(i)