はじめに

（こちらの記事は前の記事の続きとなっております。）

　この記事では、前の記事の考え方を使って、２分探索で条件を満たす最初の位置（境界）を考えます！この記事まで読むと、以下のような問題まで対応できると思います！

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

ある値x以上の最小の数のインデックスは？
ある値xより大きい最小の数のインデックスは？

前回の記事の復習

考え方

　leftとrightには探索が完了したインデックスを保持させる
このようにすることで、条件left + 1 < rightの意味や、値更新（left = mid,right = mid）がシンプルになりました。

実装

def BinarySearch_after.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

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

少し条件が変わった問題（今回）

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

ある値x以上の最小の数のインデックスは？
ある値xより大きい最小の数のインデックスは？

1. `x`以上の最小の数のインデックスは？

　今回はx = 40とします。したがって、40以上最小の数のインデックスは6となります。

ポイント

　leftとrightに探索済みのインデックスを持たせますが、leftには条件を満たさない区間を記録して、rightには条件を満たす区間を記録させます。最終的には探索対象区間を、条件を満たす区間と条件を満たさない区間に２分していくイメージです。

イメージ
探索前

    [1, 2, 9, 18, 29, 34, 44, 51, 71, 98]
 -1  0  1  2   3   4   5   6   7   8   9  10
------------------探索区間--------------------

探索後

    [1, 2, 9, 18, 29, 34, 44, 51, 71, 98]
 -1  0  1  2   3   4   5   6   7   8   9  10
                       ^   ^
-----条件満たさない-----left right--条件満たす--

実装

def BinarySearch2(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

前回の実装と比べてみてください！

def BinarySearch_after.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、rightの更新は同じなんです。違う点は探索区間を全て調べる（whileを抜けることがない）ことと、最後に条件を満たすインデックスを戻り値とすることです。このように最小限の変更で、問題に対応することができます！

2. `x`より大きい最小の数のインデックスは？

　問題１と少し異なったこちらの問題の実装は以下のようになります。
　問題１とほぼ同じです！違う点はifの条件です。

def BinarySearch3(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

実装のまとめ

　leftとrightには探索が完了したインデックスを保持させる
この考え方で、特定の１点のインデックスを求める問題だけでなく、今回のような条件を満たす区間のインデックスの特定もできるようになりました！

最後に

　２分探索は基礎的なアルゴリズムであり誰しも通るものです。その一方で、人によって様々な実装があるので、最初のうちは自分の型がなかなか身につかないと感じました。この記事を通して「２分探索わかった！」という気持ちになっていただけたら幸いです。

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