二分探索法の使い道 - Qiita

二分探索法は、検索したい値が配列の中にあるか判定するだけでなく、「所与の条件を満たす最小値を求めよ」という最適化問題にも応用でき、さらには「N個すべての値をx以下にできるか判定せよ」という判定問題にも応用が効く、使いこなせるとカッコいいアルゴリズムの一つです。 配列から目的の値を探索する二分探索法 # 二分探索法 # 計算量：O(logN) def binary_search(key, a): left = 0 right = len(a) while right >= left: mid = left + (right-left)//2 if a[mid] == key: return mid elif a[mid] > key: right = mid - 1 elif a[mid] < key: left = mid + 1 return -1 N = int(input()) a