#/***********************************************************
#    bsrch.rb -- 2分探索
#***********************************************************/
NOT_FOUND = -1

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

N = 20

a = []

printf("二分探索デモンストレーション\n")
srand(Time.new.to_i)
r = 1.0
(N-1).downto(0) do |i|
    # 1未満0以上の一様乱数をrに降順に作る 
    r *= rand() ** (1.0 / (i + 1))
    # 0以上100未満の整数に直す 
    a[i] = (100.0 * r).to_i
end
printf("  i : ")
for i in 0...N; printf(" %2d", i); end
printf("\n")
printf("a[i]: ")
for i in 0...N; printf(" %2d", a[i]); end
printf("\n")

printf("\n何を探しますか? ")
x = gets.to_i

i = bsrch(x, a, 0, N - 1)
if (i != NOT_FOUND)
    printf("i = %d\n", i)
else
    printf("見つかりません\n")
end

exit 0