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

# numbersは昇順にソート済みであることを前提とする
def binary_search(target, numbers)
  left = 0                   # 左端
  right = numbers.length - 1 # 右端
  center = nil                 # 中央値

  while left <= right do
    center = (left + right) / 2
    puts center

    # 中央の値が検索対象であった場合
    if numbers[center] == target
      return center
    end

    if numbers[center] < target
      # centerの値よりも大きい => centerより後（右）を探す
      # leftの値をcenter+1とし、検索対象を絞り込む
      left = center + 1
    else
      # centerの値よりも小さい => centerより前（左）を探す
      # rightの値をcenter-1とし、検索対象を絞り込む
      right = center - 1
    end
  end

  # 見つからなかった場合
  return -1
end

# 乱数を格納する配列を生成
numbers = []
20.times { numbers << rand(100) }

# 配列のソート
numbers.sort!

# 配列の出力
j = 0
numbers.each do |number|
  puts "#{j} : #{number}"
  j = j + 1
end

# 検索対象の問いかけ
puts "What do you search for?"

# コマンドラインからの入力の受け取り
target = STDIN.gets.chomp
#target = target.chomp

# バイナリサーチの実行
search_result = binary_search(target.to_i, numbers)

# 検索結果の出力
if search_result == -1
  puts "Could not found anything that matches \"#{target}\""
else
  puts "#{target} is found at #{search_result}"
end