バイナリーサーチの実装と解説

バイナリーサーチ（2分探索）は、ソートされた配列から特定の値を効率的に見つけるためのアルゴリズムです。このブログでは、バイナリーサーチの実装方法を具体的に説明し、実際に数字を入力したときの動作も解説します。

実装例

以下は、Rubyでのバイナリーサーチの実装例です。このコードは、ユーザーが入力した数字が配列内に存在するかどうかを確認し、存在する場合はそのインデックスを返します。

コードの解説

1. 関数定義:

   def binary_search(array, right, target)
   • array: 検索対象のソートされた配列
   • right: 配列の右端のインデックス
   • target: 検索する値

2. 初期設定:

   left = 0
   • left を配列の左端のインデックスである0に設定します。

3. ループ処理:

   while left <= right
   • left が right 以下である限り、ループを繰り返します。

4. 中央インデックスの計算:

   center = (left + right) / 2
   • center を left と right の平均値として計算します。

5. 値の比較:

   

   • array[center] が target と一致する場合、center を返します。
   • array[center] が target より小さい場合、検索範囲を右側に絞り、left を更新します。
   • array[center] が target より大きい場合、検索範囲を左側に絞り、right を更新します。

6. 値が見つからない場合:

   return -1
   • ループが終了するまでに値が見つからなかった場合、-1 を返します。

実際の動作例

以下に、具体的な数字を入力した場合の動きを示します。

例1: 配列内に数字が存在する場合

• 入力: 5
• 動作:
  • left = 0, right = 9
  • center = (0 + 9) / 2 = 4
  • array[4] = 9（検索対象より大きいので、右端を更新）
  • right = 4 - 1 = 3
  • center = (0 + 3) / 2 = 1
  • array[1] = 3（検索対象より小さいので、左端を更新）
  • left = 1 + 1 = 2
  • center = (2 + 3) / 2 = 2
  • array[2] = 5（検索対象と一致）
• 出力: 5は配列の2番目に存在します

例2: 配列内に数字が存在しない場合

• 入力: 7
• 動作:
  • left = 0, right = 9
  • center = (0 + 9) / 2 = 4
  • array[4] = 9（検索対象より大きいので、右端を更新）
  • right = 4 - 1 = 3
  • center = (0 + 3) / 2 = 1
  • array[1] = 3（検索対象より小さいので、左端を更新）
  • left = 1 + 1 = 2
  • center = (2 + 3) / 2 = 2
  • array[2] = 5（検索対象より小さいので、左端を更新）
  • left = 2 + 1 = 3
  • center = (3 + 3) / 2 = 3
  • array[3] = 6（検索対象より小さいので、左端を更新）
  • left = 3 + 1 = 4（ループ終了）
• 出力: 7は配列内に存在しません

結論

バイナリーサーチは、ソートされた配列内で特定の値を効率的に検索するための強力なアルゴリズムです。このブログでは、具体的な実装方法と、実際の入力に対する動作例を示しました。これらの例を参考に、自分のプロジェクトに応用してみてください。