Python配列二分アルゴリズム

バイセクトアルゴリズムは、リスト内の位置を見つけるために使用されます。ここで、データを挿入してリストを並べ替えることができます。 Pythonにはbisectというモジュールがあります 。このモジュールを使用すると、二分法アルゴリズムを使用できます。

このモジュールを使用するには、-

import bisect

いくつかのバイセクト関連の操作があります。これらは-

メソッドbisect.bisect（list、element、begin、end）

このメソッドは、ソートされたリスト内の位置を見つけるために使用されます。ここで、番号を配置でき、リストはソートされたままになります。要素がすでに存在する場合は、番号を挿入できる右端の位置に戻ります。

メソッドbisect.bisect_left（list、element、begin、end）

このメソッドは、bisect（）メソッドと同じです。唯一の違いは、アイテムがすでに存在する場合、このメソッドはデータを挿入するために左端の場所を返すことです。

メソッドbisect.bisect_right（list、element、begin、end）

このメソッドは、bisect（）メソッドと完全に同じです。

メソッドbisect.insort（list、element、begin、end）

このメソッドは、要素を正しい位置に挿入した後、ソートされたリストを取得するために使用されます。要素がすでに存在する場合は、リストを並べ替えたままにするために、要素が右端の位置に挿入されます。

メソッドbisect.insort_left（list、element、begin、end）

このメソッドは、insort（）メソッドと同じです。唯一の違いは、要素がすでに存在する場合、リストを並べ替えたままにするために、要素が左端の位置に挿入されることです。

メソッドbisect.insort_right（list、element、begin、end）

このメソッドは、insort（）メソッドと完全に同じです。

サンプルコード

import bisect
my_list = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]
print('Correct Location to insert 53 is: ' + str(bisect.bisect(my_list, 53, 0, len(my_list))))
print('Correct right Location to insert 69 is: ' + str(bisect.bisect_right(my_list, 69, 0, len(my_list))))
print('Correct left Location to insert 69 is: ' + str(bisect.bisect_left(my_list, 69, 0, len(my_list))))
bisect.insort(my_list, 59, 0, len(my_list))
print(my_list)
bisect.insort_left(my_list, 78, 0, len(my_list))
print(my_list)

出力

Correct Location to insert 53 is: 4
Correct right Location to insert 69 is: 8
Correct left Location to insert 69 is: 5
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120]
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]