[Python] 二分探索・線形探索アルゴリズムを書いてみた

学校でデータ処理の授業(経済学部)で、線形探索と二分探索の違いを口頭で説明されて

非常に理解しにくかったので、実際にコードを書いて理解しました。その時の備忘録です。

 

 

線形探索とは

検索アルゴリズムの1つ。リストや配列に入ったデータの検索を行う。

先頭から順番に検索を行って、見つかれば終了する。

線形探索 wikipedia

肝は、先頭から順番に検索を行うということです。

もし、探しているデータが、配列の最後にあった場合でも先頭から順番に検索していくので、

無駄な検索を行わなければならず、時間がかかるのが問題。

二分探索とは

ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

二分探索 wikipedia

wikipediaの最終文にあるように、二分探索はソートされていないリストや、大小関係が判断できない要素を含

むリストには適応できないです。

線形探索 Pythonコード

線形探索のコードを書いてみました。

 

二分探索 Pythonコード

二分探索のコードを書いてみました。

 

まとめ

実際にコードを書いてみると理解が深まりますね。

アルゴリズムをもっと勉強したくなりました。

今度は、線形探索・二分探索で実際にかかった時間を測って、比較していきたいと思います。

6 件のコメント

  • いつも読ませて頂いています。
    僕も最近プログラミングを始めました。
    まずはMacを起動させるところから頑張ります。
    これからも頑張って更新してくださいね!

    • コメントありがとうございます。
      最近、プログラミング始められたんですね!
      mac起動、ボタン押すだけですが、頑張ってください!
      これからも更新するので、よろしくお願いします。

  • いつも読んでます!
    わかりやすい説明で目から出た鱗がMacBookのキーボードに挟まりました。
    Enterキー押せません。
    これからも頑張ってください。

    • コメントありがとうございます。
      奇遇です。僕も今、鱗が挟まっています。
      僕はなんとかEnterキー押せています。
      これからも更新していくので、よろしくお願いしますmm

  • コメントを残す

    メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

    CAPTCHA