二分探索使える？

ろくに大学の授業で書いてないので、使えるかというとぶっちゃけ使えなかったんだが、今完全に理解した（ネタ）

最近、競プロでよく使うので、簡単なモジュールを書いた。

のあれ

2分探索を使う場所について

たとえば、より大きい最小の整数を求めるときとか、ソートされた配列内においてある数Xより小さい最大の数がどこにあるか知りたいときとか。割と使う場面があるんだよって学校でのくそつまんねぇ探索用途以外にもたくさんあるんだよってあの時の自分に教えてあげたい...

lower_boundとupper_bound

C++にはlower_boundとupper_boundというサクッと使えるいい感じのライブラリがある。pythonには、検索かけた感じなかった。

lower_boundというのは、訳すと下界、upper_boundは上界。数学の用語。

イメージとしてlower_boundは、ある条件を満たす配列の一番下の要素。upper_boundは、ある条件を満たすものの一番上の要素。

実装 兼 テスト

以下、蟻本をベースにした実装。

""" bound.py for util binary search """
def ge(k,array,ind):
    return array[ind]>=k

def lower_bound(k, array, func=ge):
    """
    k 以上を満たす最小のインデックスを返す
    もしなかったら要素数を返す
    """
    lb=-1
    ub=len(array)
    while ub-lb>1:
        mid = (lb+ub)//2
        if func(k,array,mid):
            ub=mid
        else:
            lb=mid
    return ub

def lt(k,array,ind):
    return array[ind]<k

def upper_bound(k, array, func=lt):
    """
    k 未満を満たす最大のインデックスを返す
    もしなかったら-1を返す
    """
    lb=-1
    ub=len(array)
    while ub-lb>1:
        mid = (lb+ub)//2
        if func(k,array,mid):
            lb=mid
        else:
            ub=mid
    return ub-1

以下、簡単なテスト

""" test_bound.py for tesging bound.py """
from bound import lower_bound, upper_bound
import unittest

class BoundTest(unittest.TestCase):
    def setUp(self):
        self.normal_array = [1,2,3,4,5,6,7]

    def test_lower(self):
        l = lower_bound(5,self.normal_array)
        self.assertEqual(l,4)

    def test_none_lower(self):
        l = lower_bound(8,self.normal_array)
        self.assertEqual(l,len(self.normal_array))

    def test_upper(self):
        u = upper_bound(5,self.normal_array)
        self.assertEqual(u,3)

    def test_none_upper(self):
        u = upper_bound(-1,self.normal_array)
        self.assertEqual(u,-1)

    def test_func_lower(self):
        l = lower_bound(34, [1,2,3,4,5,6], func=lambda k,array,ind: k<=2**array[ind])
        self.assertEqual(l,5)

    def test_func_upper(self):
        u = upper_bound(29, [1,2,3,4,5], func=lambda k,array,ind: 3**array[ind]<k)
        self.assertEqual(u, 2)

% python -m unittest test_bound.py
......
----------------------------------------------------------------------
Ran 6 tests in 0.001s

OK

うむ。 今日というか昨日esp32で2.8インチ液晶モジュールのテストをしたんだけど、思ってたより達成感というか成長感がなくてブログに書くのはやめることにした。こういうこともあるんだなぁという気持ち。