アルゴリズム

bisectの基本的な使い方と、自作方法

はじめに

標準ライブラリbisectで配列二分法（リストの二分探索）が実装されています。

今回はbisectの基本的な使い方を説明した後、自前で実装します。

bisectの基本

どこに挿入すれば良いか？

この節は、基本的な使い方を理解している方はスキップしていただいて問題ありません。

bisectは昇順ソート済みのリストに対してある値を挿入したい時、ソート状態を維持するにはどこに挿入すれば良いかを計算します。

1
2
3
4
5
import bisect
A = [2, 3, 5, 7, 11]
x = 4
ins = bisect.bisect(A, x)
print (ins)
1
2

bisectはinsertとの相性が良いです。

1
2
A.insert(ins, x)
print (A)
1
[2, 3, 4, 5, 7, 11]

bisect_leftとbisect_rightの違い

では、x = 5のように、すでにリスト内に同じ値が存在する場合はどうなるでしょうか。

1
2
3
A = [2, 3, 5, 7, 11]
x = 5
print (bisect.bisect(A, x))
1
4

リスト内に同じ値がある場合、その右側に挿入できるように位置を返します。

挿入点が左側となるような関数bisect_leftも存在します。

1
2
3
print (bisect.bisect(A, x))
print (bisect.bisect_left(A, x))
print (bisect.bisect_right(A, x))
1
2
3
4
3
4

挿入が目的であればどちらを使っても結果は変わりませんね。

bisect_leftとbisect_rightの使い分け

これらを使い分けする意味がある状況もあります。例えば、ある区間に含まれる要素を数えあげるといったシーンです。

以下のリストの中に3以上7以下の要素はいくつあるでしょうか。

1
B = [2, 2, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11]

bisect_left, bisect_rightを適切に組み合わせることで計算できます。

1
2
3
L = 3
U = 7
print (bisect.bisect_right(B, U) - bisect.bisect_left(B, L))
1
8

区間内の要素の数え上げを、閉区間・開区間の概念でまとめると以下のようになります

  • [L, U]・・・L以上 U以下
    • bisect_right(U) - bisect_left(L)
  • [L, U)・・・L以上 U未満
    • bisect_left(U) - bisect_left(L)
  • (L, U]・・・Lより大きく U以下
    • bisect_right(U) - bisect_right(L)
  • (L, U)・・・Lより大きく 未満
    • bisect_left(U) - bisect_right(L)

方針

さて、 本題のbisectの実装に入りましょう！

リスト化できない関数を探索可能な二分探索を実装し、それを元にbisectと等価な機能を実装します。

リストを直接二分探索する実装としても良いのですが、上記の方法がより汎用的なアプローチに思えるためです。

流れ

  1. 二分探索の実装
    二分探索を行う関数meguru_bisectはこちらの実装学習する天然ニューラルネットを利用させていただきました。記事の中で説明している通り、実装が簡潔でバグが入り難いと思います。

  2. bisect_leftおよびbisect_rightの実装
    実は、リスト化できない関数を探索可能な二分探索が実装できてしまうと、ここはとても楽です。
    bisect_leftとbisect_rightの違いは、等号(=)の有無だけで表現できます。

あるインデックスiが与えられた時、事前に用意している値xとリストaのi番目の値を比較するだけです。

  1. テスト
    最後に本家bisectと等しくなるかをunittestを使ってテストします。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import bisect
import unittest

def meguru_bisect(ng, ok, func):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def bisect_left(a, x):
    def func(i):
        return x <= a[i]
    return meguru_bisect(-1, len(a), func)

def bisect_right(a, x):
    def func(i):
        return x < a[i]
    return meguru_bisect(-1, len(a), func)

class TestBisect(unittest.TestCase):
    def test_bisect(self):
        test_patterns = [
            ([2,3,4,4,5,6], 6),
            ([], 6),
            ([3,3], 0),
            ([3,3], 6),
        ]
        for a, x in test_patterns:
            with self.subTest(a=a, x=x):
                self.assertEqual(bisect_left(a, x), bisect.bisect_left(a, x))
            with self.subTest(a=a, x=x):
                self.assertEqual(bisect_right(a, x), bisect.bisect_right(a, x))


if __name__=='__main__':
    a = [2,3,4,4,5,6]
    x = 6
    print (bisect_left(a, x))
    print (bisect.bisect_left(a, x))
    print (bisect_right(a, x))
    print (bisect.bisect_right(a, x))

例題

bisectを用いる良い題材として、AtCoderの問題があります。ご興味がある方は、
ABC077C Snuke Festivalをご覧ください。

記事情報

  • 投稿日：2020年4月12日
  • 最終更新日：2020年4月29日