Ruby | Arrayにindex取得をバイナリサーチで行うメソッドArray#bindexを追加する

概要

Arrayにindex取得をバイナリサーチで行うメソッドArray#bindexを追加する

詳細

Arrayにindex取得をバイナリサーチで行うメソッドArray#bindexを追加してみます。

仕様

前提
・連続データであること（ソート済み）
・値を指定すると該当一致する要素のindexを返却する

ソースコード

# encoding: utf-8

class Array
  def bindex(value, from = nil, to = nil)
    from  = 0 if from.nil?
    to  = self.size - 1 if to.nil?
    mid = (from + to) / 2
    case self[mid] <=> value
    when 0
      mid
    when 1
      bindex(value, from, mid - 1)
    when -1
      bindex(value, mid + 1, to)
    end
  end
end

テストコード

# encoding: utf-8
require_relative "../binary_search"

module ArraySpec
  describe Array do
    cases = [
      {
        input_ary: [1,2,3,4,5],
        target: 1,
        expected: 0
      },
      {
        input_ary: [1,2,3,4,5],
        target: 2,
        expected: 1
      },
      {
        input_ary: [1,2,3,4,5],
        target: 3,
        expected: 2
      },
      {
        input_ary: [1,2,3,4,5],
        target: 4,
        expected: 3
      },
      {
        input_ary: [1,2,3,4,5],
        target: 5,
        expected: 4
      }
    ]

    cases.each do |c|
      it "#bindex #{c}" do
        actural = c[:input_ary].bindex(c[:target])
        expect(actural).to eq(c[:expected])
      end
    end
  end
end