Pythonで学ぶアルゴリズム（二分探索とデータ構造） - Qiita

はじめに 本記事は、Pythonによるアルゴリズム（二分探索とデータ構造）の検証結果のまとめです。 仮説 二分探索をPythonで記述する場合、合わせてデータ構造を考慮すると、Pythonでもリストより配列の方が早いと考えました。配列の場合、連続的にメモリのアドレスを確保し、ランダムアクセスやすべての要素を瞬時に調べることができるためです。対して、リストだと10番目の要素を読み取りたい場合は、9番目の要素を読み取って10番目の要素をたどる必要があるなど、総合的に配列の方が早いと思いました。 検証 1億個の要素から、目的の要素を見つけるのにかかる計算時間を計測します。 まずは、学習がてら単純探索より、二分探索が早いことを確認します。 次に、二分探索でリストと配列の場合での計算時間を計測します。 環境：MacBook Air プロセッサ名:Intel Core i5 プロセッサ速度:1.6 G