【アルゴリズム】配列内を早く検索する！【二分探索】

図とコード(PHP)を使って解説していきます 図解例えば以下のような配列が存在し、数値の21を探したいとします。 ※配列の中はあらかじめソートされていると前提します。 上記の配列から特定の数字を探す場合、どういった方法が良いのでしょうか？ 通常探索まず順番に探していく場合、下記のとおりになります。 ご覧の通り、順番に探していく場合はかなり手間になります。 二分探索の場合はどうでしょうか。 まず配列の真ん中にある数値を探索します。 今回だと「(0 + 10) / 2 = 5」になるので配列の真ん中は[5]であることが分かります。 配列[5]の中には数値15が入っています。探したい数値は21なのでまだ正解にはたどり着いていません。 しかし、配列[5]以降に探している数値21はあることが分かりました。 次は配列[6]から[10]の真ん中を見に行きます。 「(6 + 10) / 2 = 8」になる