【Python】二分探索を実装する【アルゴリズム】

この記事は約3分で読めます。

二分探索の概要

  • 探索したい値とデータの中央の値を大小比較し、半分に絞り込んでいく
  • 探索の対象となるデータが昇順にソートされている必要がある。
  • 計算量はO(logn)

二分探索の実装

 

二分探索の実装(補足付)

こちらは前述のコードに補足をつけたものです。

 

二分探索でAtcoderに挑戦(ABC 212 C問題)

問題:Atcoder Beginnger Contest 212 C問題

問題については公式サイトをご覧ください。

解答についてはこちらの記事で書きました。

解法1:bisectを用いる

この記事は二分探索についてのものですが、bisectというライブラリが作成されています。

自身で実装する必要がないので、実務やAtcoderで二分探索を使うことがあればこちらを利用した方が早いです。

解法2:自分で二分探索を実装して解く

自身で実装する必要はないのですが、せっかくなので自分で二分探索を実装した上で解いてみました。

意味があったかはともかく、bisectと今回の記事で書いた二分探索のコードは異なる点があることがわかりました。

bisectではリスト内に探索対象となる値が含まれていない場合、mid+1の要素番号を返しているように見えます。

一方、こちらの記事で実装した二分探索ではmidの要素番号を返します。

細かい違いですが、同じ二分探索を実装する場合でも人によって違いがあることがわかりました。

ライブラリを利用して別の問題を解いたり実装を行う際は、ライブラリの中身が異なることで、それ以外の部分もコードが異なってきそうです。

現在の私の仕事でコードを書くことは少なく、せいぜい自身の業務効率化のためにちょっとしたプログラムを書く程度ですが、もし同僚と一緒にコードを書く機会に恵まれた場合は、注意したいと思います。

参考書籍

こちらの書籍を参考にさせて頂きました。

今回の記事では書ききれていない詳細な説明がある点、二分探索以外の探索手法についても体系的にまとめられている点、Atcoderを解いていく上で必須の計算量についても解説されている点など、Pythonの学習者にとっては購入して損はないと考えています。

ネットに記載されている情報もこちらの本を参考にしていると思われる記事もあります。ネット全盛の現代でも、体系的に情報を得るためには書籍は高い価値を持っていると思います。

競技プログラミングに取り組む上では蟻本と呼ばれるこちらの書籍が推奨されていますが、言語はPythoではなくC++が使われています。C++はPythonよりも早いということで、AtcoderでもC++を使用している方が多いですが、Pythonしか使ったことのない私には難しく、先ほど記載した本で勉強しています。

コメント