二分探索の処理をじっくり追ってみる

7920 ワード
AtCoder アルゴリズム アルゴリズム テキストリンク

概要

atcoder でも頻出テーマである二分探索に関する内容です．

はじめに

二分探索は、比較的シンプルな手法ではありますが、実装でつまずくことが多いのではないかと感じています．

二分探索における処理の流れをじっくり理解することを目的に，二分探索のサンプルの問題を一つ取り上げて，実装時の処理を一つずつたどり，二分探索において使用される変数の理解を深めることを目的としています．
(次回, コンテストで2分探索が出題されたときの実装に困らないように．．．）
二分探索のアルゴリズムの説明などはこちらなどの別記事をご参照ください．

サンプル問題

競プロ典型 ９０問の第１問のケースを取り上げます．

コード(py)

※基本的にこちらのc++のコードをpython に書き換えたコードとなっています．
https://qiita.com/e869120/items/1b2a5f0f07fd927e44e9

Main.py
n, l = map(int, input().split())
k = int(input())
a = list(map(int, input().split()))

def solve(mid):
    """ ある羊羹の切れ目の間隔の最小値候補が条件を満たすか否かを判定する
    Args:
        mid (int): [羊羹の切れ目の間隔の最小値候補]
    Returns:
        boolean: [判定対象のindex が条件を満たすかどうか]
    """
    tmp_val = 0 # 切った羊羹の長さ
    cut_cnt = 0 # 羊羹を切る数
    for i in range(n):
        if a[i] - tmp_val >= mid and l - a[i] >= mid:
            cut_cnt += 1
            tmp_val = a[i]
    if cut_cnt >= k:
        return True
    else:
        False
right = l
left = 0
while right - left > 1:
    mid = (right + left) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
print(left)

以下のサンプルケースで考えます．

7 45
2
7 11 16 20 28 34 38

while処理おけるleft, right, mid の各変数の値の遷移

left(条件を満たす範囲) mid (各ステップにおける判定対象) right(条件を満たさない範囲)
0 22⤷ 45
0 ⤶11 22
11 16⤷ 22
11 13⤷ 16
11 ⤶12 13
12 12 13

各mid の値をleft, もしくは，right に振り分けているようにも見えますね．
left は条件を満たす最大値となっています． > つまり，この問題の答えとなっています．
一方，right は条件を満たさない最小値です．

最後のwhile文の処理をする時点においては，

  • right = 13
  • left = 11
  • mid = 12

right - left = 2 > 1より，while 文を継続します．

while文の終了時においては，

  • right = 13 ... (条件を満たさない最小値)
  • left = 12 ... (☆:このサンプルケースの答え)
  • mid = 12

right - left = 1 より， while 文を終了します．

このように，最終的には，

  • left に条件を満たす最大値が格納され，
  • right に条件を満たさない最小値が格納されていることがわかります．

処理フロー



まとめ

単に二分探索を実装するだけであれば， めぐる式二分探索と呼ばれる実装の流派[link]やPythonの標準ライブラリのbisectモジュールを使って実装することもできますね.

自分なりの二分探索の実装方法を身に着けることが一番自分の力になるかなと思います．