二分探索（binary search）

概要

データ探索アルゴリズムの1つ。
探索対象はソート済みのデータ群。
探索範囲を半分に絞り込む作業を繰り返す。

半分に絞り込む作業

①探索範囲の中心の値を比較する。
②探索対象より大きい場合は中心より左に存在する。
③探索対象より小さい場合は中心より右に存在する。
以下の図の黄背景は3、赤背景は12を探した場合のイメージ図

public static int Exec(List<int> numbers, int target)
{
  var left = 0;// 紫文字
  var right = numbers.Count - 1;// 赤文字
  
  while()
  {
    var half = left + (right - left) / 2;// ①
    var number = numbers[half];
    if (number == target)
      return half;
      
    if (target < number)// ②
      right = half - 1;
    else// ③
      left = half + 1;
  }
}

終了条件

上記は対象が必ず存在しない場合は無限ループになってしまう。
以下の図の黄背景は2, 赤背景は16を探した場合のイメージ図
濃い背景色の箇所が探索の打ち切り箇所で、探索対象の左端が右端以上になった場合は終了する

public static int Exec(List<int> numbers, int target)
{
  var left = 0;// 紫文字
  var right = numbers.Count - 1;// 赤文字
  
  while(left < righ)
  {
    var half = left + (right - left) / 2;// ①
    var number = numbers[half];
    if (number == target)
      return half;
      
    if (target < number)// ②
      right = half - 1;
    else// ③
      left = half + 1;
  }
}

計算量

以下の図のように検索対象を半分にしていく。

データ数8に対して3回繰り返すことによってデータを見つけることができた。
log₂8 = O(logn)