Pythonでbisectを用いてソートされたリスト内での値の挿入と検索

スポンサーリンク

Pythonでbisectを用いてソートされたリスト内での値の挿入と検索を行ってみます。

今回はbisectを用います。このライブラリ・モジュールはPythonの標準ライブラリですので、事前にインストールする必要はありません。

■Python

今回のPythonのバージョンは、「3.10.9」を使用しています。(Windows11)(pythonランチャーでの確認)

■リストに対して要素を挿入する位置の発見と挿入

Pythonでbisectを用いてリストに対して要素を挿入する位置の発見と挿入するスクリプトを書いていきます。

■コード

import bisect

# ソートされたリストの中に要素を挿入する例
def insert_into_sorted_list(sorted_list, value):
    index = bisect.bisect_left(sorted_list, value)
    bisect.insort_left(sorted_list, value)
    return index

sorted_numbers = [1, 3, 5, 7, 9]
new_value = 6
insert_index = insert_into_sorted_list(sorted_numbers, new_value)

print(f"{new_value} を挿入した後のリスト: {sorted_numbers}")
print(f"{new_value} の挿入インデックス: {insert_index}")

# ソートされたリスト内での値の検索例
def find_value(sorted_list, value):
    index = bisect.bisect_left(sorted_list, value)
    if index < len(sorted_list) and sorted_list[index] == value:
        return index
    else:
        return -1

value_to_find = 7
found_index = find_value(sorted_numbers, value_to_find)

if found_index != -1:
    print(f"{value_to_find} はリストのインデックス {found_index} にあります。")
else:
    print(f"{value_to_find} はリスト内に見つかりませんでした。")

bisectモジュールをインポートします。このモジュールは、ソートされたシーケンス(リストやタプルなど)に対して挿入や検索を効率的に行うための関数を提供します。

その後、insert_into_sorted_list(sorted_list, value)と記述し、ソートされたリストに新しい要素を挿入するための関数を定義します。引数,パラメータとしてはsorted_list(ソートされたリスト)、value(挿入する要素の値)を渡します。

関数内部では、bisect.bisect_left(sorted_list, value)で、valueを挿入するための適切な位置を求めます。これはsorted_list内でvalueがどこに挿入されるべきかを示すインデックスです。次に、bisect.insort_left(sorted_list, value)を使用して、そのインデックスにvalueを挿入します。最後に、挿入されたインデックスを返します。

関数を定義後、sorted_numbers = [1, 3, 5, 7, 9]と記述し、ソートされた数値のリストを定義します。

定義後、new_value = 6と記述し、挿入する新しい値を定義します。今回は値を「6」とします。

定義後、insert_index = insert_into_sorted_list(sorted_numbers, new_value)と記述し、insert_into_sorted_list関数を呼び出して新しい値を挿入し、挿入されたインデックスを取得します。

取得後、print(f”{new_value} を挿入した後のリスト: {sorted_numbers}”)と記述し、挿入が行われた後のリストを表示します。同じく、print(f”{new_value} の挿入インデックス: {insert_index}”)と記述し、挿入された位置(インデックス)を表示します。

次に、find_value(sorted_list, value)と記述し、ソートされたリスト内で特定の値を検索するための関数を定義します。引数,パラメータとしてはsorted_list(ソートされたリスト)、value(検索する値)を渡します。

関数内部では、bisect.bisect_left(sorted_list, value)で値の挿入位置を求め、その位置の値をチェックして実際に値が存在するか確認します。存在する場合はインデックスを返し、存在しない場合は-1を返します。

関数を定義後、value_to_find = 7と記述し、検索する値を定義します。今回は値を「7」とします。

その後、found_index = find_value(sorted_numbers, value_to_find)と記述し、find_value関数を呼び出して値の検索を行い、結果のインデックスを取得します。

最後に、検索結果に基づいて値が見つかったかどうかを表示します。

■実行・検証

このスクリプトを「b_i_s.py」という名前で、Pythonが実行されている作業ディレクトリ(カレントディレクトリ)に保存し、コマンドプロンプトから実行してみます。

実行してみると、bisectを用いてソート済みリストに値を挿入し、その後リスト内で指定した値の検索を行い、検索結果を出力させることができました。

コメント

タイトルとURLをコピーしました