Rubyで指数探索を実装してみた

はじめに

以下の指数探索の記事を見かけ、興味を持ちました。
二分探索よりも速い指数探索の解説
この記事では、上記の記事においてC++で実装されていた指数探索を、Rubyで実装してみました。

ソースコード

exponential_search.rb

class Exponential_search
  def initialize(array)
    @array = array.sort # 配列は事前にソートしておく
  end

  def exponential_search(first,last,key)
    # 指数探索の開始
    len = @array.size
    prev = first
    cur = prev + 1
    dis = 1
    while dis < len and @array[cur] < key
      prev = cur
      cur += dis
      dis *= 2
    end
    exponential_search_last = dis < len ? cur : last
    binary_search(prev,exponential_search_last,key)
  end

  def binary_search(first,last,key)
  # ２分探索のメソッド
    while first <= last
      mid = (first + last) / 2
      return @array[mid] if @array[mid] == key
      if @array[mid] < key
        first = mid + 1
      else
        last = mid - 1
      end
    end
  end
end

実行速度の評価

実装した指数探索の計算速度を、二分探索と比較してみました。
探索対象として、1〜1000までの整数の中から重複なしでランダムに500個取り出したデータを用意しました。

探索した数	指数探索での探索時間（ミリ秒）	二分探索での探索時間（ミリ秒）
10	0.1417	2.0549
500	2.5296	0.1498
900	0.1607	0.1425