[Python]二分探索(bisect) ABC143D - Qiita

当内容は、他サイトを参考に自分用に編集したものです。 二分探索の動機 ソートされたリストに対してソート順序を保ったまま値を挿入したいと思う場面は少なくないはずです。そういった場面に 出くわしたときにappendしてsortしているとパフォーマンスはよくないです。Pythonのlistのソートの平均時間計算量は$O(n \log{n})$です。要素数が増えてきたり、毎度ソートしていたりすると実行速度にも影響がでてくると思います。 A = [1, 12, 23, 38, 54, 66, 76, 98] # Aの順序を保ったまま'46'を挿入したい A.append(46) A.sort() print(A) # [1, 12, 23, 38, 46, 54, 66, 76, 98] 今回は、上記の方法よりも効率よく、ソートされたリストに対してソート順序を保ったまま値を挿入する二分探索法のPyt