binary_search.rb

Heads up: This description was created by AI and might not be 100% accurate.

このRubyスクリプトは、バイナリサーチ（二分探索）アルゴリズムを実装したものです。プログラムの特徴は、ソート済みのデータ配列から特定のターゲット値を効率的に検索することです。

アルゴリズム:

初期化:
- min_index: 検索範囲の最小インデックスを0に設定。
- max_index: 検索範囲の最大インデックスを配列の長さを1減算した値に設定（配列の最後の要素を含む）。
反復:
- whileループは、min_indexがmax_index以下である限り実行されます。この条件が満たされない場合、ターゲット値が配列内に存在しないことを意味します。
中央インデックスの計算:
- mid_index = min_index + (max_index - min_index) / 2
- 中央インデックスを計算します。この計算方法は、オーバーフローを避けるためのものです。
値の比較:
- standard = data[mid_index]：中央インデックスにある要素の値を取得。
- if standard == target：中央要素の値がターゲット値と一致する場合、mid_index（ターゲット値のインデックス）を返します。
- elsif standard < target：中央要素の値がターゲット値より小さい場合、ターゲット値は中央要素よりも大きい要素の範囲にあるため、min_indexをmid_index + 1に更新して、検索範囲を右半分に絞り込みます。
- else：中央要素の値がターゲット値より大きい場合、ターゲット値は中央要素よりも小さい要素の範囲にあるため、max_indexをmid_index - 1に更新して、検索範囲を左半分に絞り込みます。
ターゲットが見つからない場合:
- whileループが終了し、ターゲット値が配列内に存在しない場合、-1を返します。

コードの説明:

binary_search(data, target): data（ソートされた配列）と target（検索する値）を受け取る関数です。
data.sort!: data配列をインプレースでソートします。
p binary_search(data, 34): data配列を34で検索し、結果を標準出力に出力します。
p binary_search(cities, "sapporo"): cities 配列を “sapporo” で検索し、結果を標準出力に出力します。

このコードは、効率的な検索アルゴリズムであるバイナリサーチを利用し、ソート済みの配列に対して、平均計算量O(log n)でターゲット値を検索します。

Ruby code snippet

# frozen_string_literal: true
#=> nil

def binary_search(data, target)
  min_index = 0
  max_index = data.length - 1

  while min_index <= max_index
      mid_index = min_index + (max_index - min_index) / 2
      standard = data[mid_index]
  
      if standard == target
          return mid_index
        elsif standard < target
          min_index = mid_index + 1
        else
          max_index = mid_index - 1
      end
  end
  -1
end
#=> :binary_search

data = [0, 1, 34, 56, 78]
#=> [0, 1, 34, 56, 78]
data.sort!
#=> [0, 1, 34, 56, 78]
p binary_search(data, 34)
2
#=> 2

cities = %w[fukuoka hiroshima kobe kyoto nagoya osaka sapporo tokyo yokohama]
#=> 
["fukuoka",

p binary_search(cities, "sapporo")
6
#=> 6

Executed with Ruby 3.4.9.