表題の件についてまとめる
よく使う配列のアルゴリズムである。
線形探索
線形探索は、「配列からデータを探索する「アルゴリズム」。配列の前から順番にデータを検索する。 配列の中身はなんでも良いのですが、ここでは数値を例に説明。該当の数値を6とする。
左側の数値と該当の数値を比較してm、合致すれば探索は終了する。
合致しなければ、左→右へと数値を探索する
2分探索
2分探索は、ソート順に並んでる配列に扱うことができるアルゴリズムである。該当の数値を特定するために、まず2分割する。
探す該当領域が1/2になる。
該当の数値は小さい順に左から並んでるため、その都度数値を比較し該当数値がどこにあるのかを定めていく。
初めの1/2にする際も真ん中の数値が何番目であるか、を算出して比較していく
2分探索は配列がソートされていることを利用し、探索範囲を半分ぶつに減らしていく方法である。
探索するデータが1個になった時に探索は終了する!
元々あるデータnを半分ずつにするために Log2 N回繰り返せばデータは1個になる。
つまり、2分探索では「配列の真ん中の値と比較して、探索範囲を繰り返し半分にする操作」をlog2 N回繰り返せばデータを見つけることができる。