150111

Ruby


「アルゴリズムとデータ構造」のRuby版。

バイナリサーチ

# -*- coding: cp932 -*-

NOT_FOUND = -1

N = 10

def binary_search(x, a, left, right)

  while left <= right

    mid = (left + right) / 2

    return mid if a[mid] == x

    if a[mid] < x 

      left = mid + 1

    else

      right = mid - 1

    end

  end

  return NOT_FOUND

end

# 適当な配列を作る

array = []

printf("array ")

printf("[0]:%d ", array[0] = rand(3))

for i in (1..N - 1)

  printf("[%d]:%d ", i, array[i] = array[i - 1] + rand(3))

end

printf("\n何を探しますか:")

i = gets().to_i

r = binary_search(i, array, 0, N - 1)

if r == NOT_FOUND

  printf("%dは見つかりません\n", i)

else

  printf("%dは%d番目です\n", i, r)

end

バイナリサーチ（lower_bound）

# -*- coding: cp932 -*-

NOT_FOUND = -1
N = 10

def binary_search(x, a, left, right)
  while left < right
    mid = (left + right) / 2
    if a[mid] < x
      left = mid + 1
    else
      right = mid
    end
  end
  return left if a[left] == x
  return NOT_FOUND
end

# 適当な配列を作る
array = []
printf("array ")
printf("[0]:%d ", array[0] = rand(3))
for i in (1..N - 1)
  printf("[%d]:%d ", i, array[i] = array[i - 1] + rand(3))
end
printf("\n何を探しますか:")
i = gets().to_i
r = binary_search(i, array, 0, N - 1)
if r == NOT_FOUND
  printf("%dは見つかりません\n", i)
else
  printf("%dは%d番目です\n", i, r)
end