競プロ典型90問 001 - Yokan Party - Qiita

問題 競プロ典型90問 001 Yokan Party 解法 使用する考え方 二分探索法 貪欲法 二分探索法 ソートされた複数のデータの中からあるデータを探す際に、中央値よりも大きいか小さいかで探す範囲を絞っていく方法。 また、何番目のデータか探すだけではなく、何番目と何番目の間に入るかを調べることもできる。 先頭から見ていくよりもかなり速い。 例 list = [1,2,4,8,16] lo = 0 hi = len(list) search = 1 while hi - lo > 1: mid = (lo+hi)//2 if list[mid] <= search: lo = mid else: hi = mid print(lo) #3 1回目は0番目~4番目を調べるため、中央値である2番目の4との大小を比較する。 4より大きいので次は3番目~4番目の数字を調べる。 3番目と4番目の