【2分探索】 ~ 境界探索の実装まで ~

はじめに

今回の記事のテーマは２分探索です。競技プログラミングでたまに実装するので、発展した問題まで対応できる考え方・実装を考えます。

２分探索

探索対象が単調列になっている時に使用することができます。計算量がO(log(N))であり、線形探索O(N)と比べて非常に高速です。

問題

配列 li = [1,2,9,18,29,34,44,51,71,98]があります。

1. ある値xのインデックスを求めてください。
2. ある値x以上の最小の数のインデックスを求めてください。
3. ある値xより大きい最小の数のインデックスを求めてください。

このような問題に対しての実装を考えます。値１つのインデックスを求めるだけではなく、境界を求める問題も考えます。この時、値１つのインデックスを求める際の考え方・実装をできるだけ変えずに、境界を求める実装をしたいと考えます。

考え方

leftとrightには探索が完了したインデックスを保持させる

ポイントはleftとrightには探索済みのインデックスの値をそれぞれ代入します。イメージは下の図の通りです。leftが4を保持していることは、「ここまではもう探索済みだよ！」ということを表しています。rightも同様です。

   [1, 2, 9, 18, 29, 34, 44, 51, 71, 98]
-1  0  1  2   3   4   5   6   7   8   9  10
                  ^           ^
------探索済み----left       right---探索済み---

実装

1. ある値xのインデックスを求めてください。

def BinarySearch.py(x,li): 
    left = -1; right = len(li)
    while left +1 < right:
        mid = (left+right)//2
        if li[mid] == x: return mid
        elif li[mid] > x: right = mid
        elif li[mid] < x: left = mid
    return -1

• while条件の意味
  left + 1 < rightの意味は探索対象区間がなくなるまで、です。条件が偽になるときはleftとrightが隣り合うとき、すなわち探索対象区間がないときです。
• 値の更新がシンプル
  left = midやright = midで区間を狭めるときの値の更新がシンプルです。

2. ある値x以上の最小の数のインデックスを求めてください。

def BinarySearch(x,li): 
    left = -1; right = len(li)
    while left + 1 < right:
        mid = (left+right)//2
        if li[mid] >= x: right = mid
        elif li[mid] < x: left = mid
    return right

値１つのインデックスを求めるときと、whileの条件、leftとrightの更新という点で同じです。この問題のように境界を求める問題は、ループを最後まで抜けることはないのでそこが違います。

3. ある値xより大きい最小の数のインデックスを求めてください。

def BinarySearch(x,li):
    left = -1; right = len(li)
    while left + 1 < right:
        mid = (left+right)//2
        if li[mid] > x: right = mid
        elif li[mid] <= x: left = mid
    return right

前の問題とほとんど実装が同じです！違う点はifの条件です。

最後に

２分探索は基本的なアルゴリズムですが掘り下げると面白いです。これで競技プログラミングで２分探索の問題が出てきたら最高です！

最後まで読んでいただきありがとうございました！