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

初心者向けにPythonにおけるbisect()の利用方法について現役エンジニアが解説しています。bisectとは、二分探索法と呼ばれるアルゴリズムを実現するPythonのライブラリです。全てを順番に全件検索する線形探索法(リニアサーチ)と比べて計算速度が速いのが特徴です。

TechAcademyマガジンはオンラインのプログラミングスクールTechAcademy [テックアカデミー]が運営する教育×テクノロジーのWebメディアです。初心者でもすぐ勉強できる記事が2,000以上あります。

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

Pythonについてよく分からないという方は、Pythonとは何なのか解説した記事みてみましょう。

 

なお本記事は、TechAcademyのPythonオンライン講座の内容をもとにしています。

 

田島悠介

今回は、Pythonに関する内容だね!

大石ゆかり

どういう内容でしょうか?

田島悠介

Pythonにおけるbisect()の利用方法について詳しく説明していくね!

大石ゆかり

お願いします!

 

bisect()とは?

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

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

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

 

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

 

 

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

 

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

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

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

bisect()の使い方

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

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

import bisect

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

bisect(list, value)

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

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

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

 

[PR] Pythonで挫折しない学習方法を動画で公開中

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

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

20を挿入してみると、

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

となります。

 

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

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

 

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

しかし、この場合でも考え方は同じで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、データプロダクトの開発経験あり。

 

大石ゆかり

Pythonにおけるbisect()の利用方法がよくわかりました!

田島悠介

ゆかりちゃん、これからも分からないことがあったら質問してね!

大石ゆかり

分かりました。ありがとうございます!

 

オンラインのプログラミングスクールTechAcademyではPythonを使って機械学習の基礎を学ぶPythonオンライン講座を開催しています。

初心者向けの書籍を使って人工知能(AI)や機械学習について学ぶことが可能です。

現役エンジニアがパーソナルメンターとして受講生にマンツーマンのメンタリングで学習をサポートし、最短4週間でweb開発のスキルを習得することが可能です。

また、現役エンジニアから学べる無料のプログラミング体験会も実施しているので、参加してみましょう。