Pythonにおけるbisect()の利用方法を現役エンジニアが解説【初心者向け】

Pythonにおけるbisect()の利用方法について解説します。

そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。

 

なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。

 

 

bisect()とは？

bisectとは、二分探索法と呼ばれるアルゴリズムを実現するPythonのライブラリです。

bisectライブラリの中に、bisect関数、bisect_left関数、insort関数などが入っており、今回の記事ではbisect関数を扱います。

二分探索法とは、値が昇順、降順に並べられたリストの中から、ある要素を見つける問題に対して、効率よく解くことができるアルゴリズムです。

 

この問題を解くためのアルゴリズムは、for文でリストの中身と見つけたい要素を１つずつ一致しているか確かめるものです。これは線形探索法と呼ばれ、二分探索法と比べて非常に計算速度が遅いというデメリットがあります。

 

 

二分探索法の直感的な例として、裏返しに昇順(小さい順)に並べられた数字のカードを考えてみましょう。例えば、カードの中から21を見つけたいとします。適当に一枚めくったその数が21より小さい場合、次はそのカードよりも右のカードを探せば良いといえます。
そして、一回の操作で、めくったカードより左のカードはもう考えなくて良いといえるでしょう。

 

大きい場合は、その逆でめくったカードより右のカードはもう考えなくて良いといえます。

このような操作を繰り返すことで巨大な配列な中から非常に効率的に見つけたい要素を発見できます。

なお、bisect関数はリストに値を挿入した時のインデックスを返すものです。

bisect()の使い方

まず、bisect関数はPythonの標準ライブラリであるbisectモジュールの中に格納されています。

そのため、importを行いましょう。

import bisect

次に、bisect関数自体の使い方をみていきます。

bisect(list, value)

という２つの引数を取り、listは元の配列、valueは配列に挿入したい値です。

そして、挿入した際のインデックスを返します。

正確には、bisectの返り値は、valueは配列listに含まれるvalueのうち、どの要素よりも右に来るインデックスです。

 

[PR] 未経験からWebエンジニアを目指す方法とは

bisect()を利用してデータを探索する

それでは実際にbisect関数を使っていきましょう。

降順も同じであるため、今回の例では昇順のみ考慮します。

import bisect
list1 = [1, 4, 6, 8, 9, 12, 15, 20, 25, 47]
value1 = 20
print(bisect.bisect(list1, value1))
# 8
list2 = [1, 1, 4, 5, 6, 8, 8, 8, 8, 9, 9, 9]
value2 = 8
print(bisect.bisect(list2, value2))
# 9
list3 = [2, 4, 6, 8, 10, 12, 14]
value3 = 7
print(bisect.bisect(list3, value3))
# 3

１つ目の例では、リストは昇順に並んでおり、要素に重複はありません。

20を挿入してみると、

[1, 4, 6, 8, 9, 12, 15, 20, 20, 25, 47]

となります。

 

ここで、返り値の定義は、「配列listに含まれるvalueのうち、どの要素よりも右に来るようなインデックス」です。

そのため、20のうちもっとも右にある20のインデックスは8なので、8が返り値として返ってきます。

 

２つ目の例は、要素に重複があるタイプです。

しかし、この場合でも考え方は同じで8を挿入してみると、

[1, 1, 4, 5, 6, 8, 8, 8, 8, 8, 9, 9, 9]

となり、もっとも右にある8のインデックスは9に変化します。

 

3つ目の例は、配列の中に探したい値が含まれていないケースです。

これも考え方は同じです。

値を挿入してみると、

[2, 4, 6, 7, 8, 10, 12, 14]

となり、もっとも右にある7のインデックスである3が返ってきます。

監修してくれたメンター

菊田俊平（きくたしゅんぺい） AIリサーチャー・AIエンジニア。 大学での研究と、スタートアップ企業でAIの開発を行う。推薦システム、動画の分類API、データプロダクトの開発経験あり。

 

 

TechAcademyでは、初心者でもPythonを使った人工知能（AI）や機械学習の基礎を習得できるオンラインブートキャンプPython講座を開催しています。

挫折しない学習方法を知れる説明動画や、現役エンジニアとのビデオ通話とチャットサポート、学習用カリキュラムを体験できる無料体験も実施しているので、ぜひ参加してみてください。