Rubyでアルゴリズムやらデータ構造やらのお勉強（Linear Search）

linear_search.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

$VERBOSE = true

class Array

  # これだと番兵とか登場しないので・・・
  def linear_search_index(target)
    each_with_index do |value, index|
      return index if target == value
    end

    nil
  end

  # 今回はあえてwhileやloop・・・本当はこういう書き方したくないからRubyを使うんだけども。
  def not_enum_linear_search_index(target)
    index = 0
    while index < length
      return index if target == self[index]
      index += 1
    end

    nil
  end

  # 番兵と目標が一致したら最後の要素戻しやんなくてもいい気がするけど、書籍でもとりあえず戻してる感じだった。
  # 分り易くするためなのか、安全性を重視した為なのかちょっと気になる。
  def not_enum_with_sentinel_linear_search_index(target)
    true_last = pop
    push target

    index = 0
    loop do
      break if target == self[index]
      index += 1
    end

    pop
    push true_last
  
    if index == (length - 1)
      (target == true_last) ? index : nil
    else
      index
    end
  end

end

# Overview

p %w[a b c d e].linear_search_index('d') #=> 3
p %w[a b c d e].linear_search_index('e') #=> 4
p %w[a b c d e].linear_search_index('f') #=> nil

p %w[a b c d e].not_enum_linear_search_index('d') #=> 3
p %w[a b c d e].not_enum_linear_search_index('e') #=> 4
p %w[a b c d e].not_enum_linear_search_index('f') #=> nil

p %w[a b c d e].not_enum_with_sentinel_linear_search_index('d') #=> 3
p %w[a b c d e].not_enum_with_sentinel_linear_search_index('e') #=> 4
p %w[a b c d e].not_enum_with_sentinel_linear_search_index('f') #=> nil