Rubyで線形探索と二分探索を出力する

こんにちは、Ruby歴半年のプログラマです。

基本的なアルゴリズムを習得したいと考えて、『Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量』を読んでいます。

本記事は『Pythonではじめるアルゴリズム入門』のPythonの線形探索と二分探索のサンプルコードをRubyで実装しました。

より良いコードの書き方などありましたら教えてもらえると嬉しいです。

環境

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.15.4
BuildVersion:   19E287
$ ruby -v
ruby 2.7.0p0 (2019-12-25 revision 647ee6f091) [x86_64-darwin19]

Rubyで線形探索

def binary_search(data, input_number)
  data.each_with_index do |number, index|
    return index if number == input_number
  end
end

data = [10, 20, 30, 40, 50, 60, 70, 80, 90]
p binary_search(data, 40)
# -> 3

Rubyで二分探索

def binary_search(data, input_number)
  first_point = 0
  last_point = data.count - 1
  # 始点が終点よりも小さい間繰り返し処理をする
  while first_point <= last_point
    # 中央位置は始点と終点の間
    base_point = (first_point + last_point).div(2)
    if data[base_point] == input_number
      return base_point
    # 中央点が探索している数値よりも大きければ終点の位置を中央位置の右側にずらす
    elsif data[base_point] > input_number
      last_point = base_point - 1
    # 中央点が探索している数値よりも小さければ始点の位置を中央位置の左側にずらす
    else
      first_point = base_point + 1
    end
  end
end

data = [10, 20, 30, 40, 50, 60, 70, 80, 90]
p binary_search(data, 40)
# -> 3
p binary_search(data, 80)
# -> 7

探したい値input_numberと中央位置data[base_point]との大小比較によって始点first_pointや終点last_pointの値を更新する処理がポイントですね。