はじめに
会社の研修でアルゴリズムの研修をしているので、備忘録として線形探索と二分探索について書こうと思います。
アルゴリズムって？
問題を解決するための方法や手順のこと。問題解決の手続きを一般化するもので、プログラミングを作成する基礎となる。アルゴリズムは1つの問題に対し、複数ある場合が多い。
コトバンクによればこんな感じです。
例として料理におけるレシピのようなもので、特定の料理を作るためのの手順がレシピだとすれば特定の問題をコンピュータで解くための手順がアルゴリズム。
線形探索
線形探索は配列からデータを探索するアルゴリズム。
配列の先頭から順番にデータを調べていくので、ソート（整列）していない乱雑なデータにも用いることができる。
データ数が多く、目的のデータが後ろにある場合や目的のデータが存在しない場合は時間がかかってしまう。
2分探索
同じく、配列からデータを探索するアルゴリズム。
データがソートされている場合にのみ適用できる。
配列の真ん中あたりのデータと目的のデータを比較することにより探索範囲を半分に絞ることができる。
これを目的のデータが見つかるか、存在しないことがわかるまで繰り返す。
計算時間は線形探索に比べ圧倒的に早い。
コスト
二分探索を行うためには常にデータをソートしておく必要があるため、データを追加する際は配列をメンテナンスするためのコストがかかる。
一方、線形探索の場合は追加に気を使わず、最後尾にくっつけるだけなのでコストがかからない。