어떤 사람들은 알고리즘이 명확하면 그의 구현은 간단하다고 말하지만, 실제로는 그렇지 않다. Knuth는 TAOCP의 Sorting and Searching에서 binary search는 1946년에 발표되었으나, 그의 정확한 구현은 1962년에 이루어졌다고 지적하였다.(Proramming Pearls중 일부를 발췌/편역)

정말 그런가 구현해 봅시다.. 아래는 제가 구현한 답입니다. 답을 보시려면, 먼저 구현해보세요!! ㅎㅎ

require “test/unit/testcase”

def binary_search(list, val)
left = 0
right = list.size – 1

while (left <= right) mid_idx = (left + right) >> 1
mid_item = list[mid_idx]

if val < mid_item right = mid_idx - 1 elsif val > mid_item
left = mid_idx + 1
elsif val == mid_item
return mid_idx
end

end

return -1
end

class BinarySearchTest < Test::Unit::TestCase def setup @list_1_9 = (1..9).to_a @list_1_10 = (1..10).to_a end def test_existing @list_1_9.each { |i| assert_equal(binary_search(@list_1_9, i), i - 1) } @list_1_10.each { |i| assert_equal(binary_search(@list_1_10, i), i - 1) } end def test_non_existing assert_equal(binary_search(@list_1_9, -1), -1) assert_equal(binary_search(@list_1_9, 10), -1) assert_equal(binary_search(@list_1_10, -1), -1) assert_equal(binary_search(@list_1_9, 11), -1) end def test_random 1.upto(1000) do list = [] 1.upto(1000) do list << rand(1000) end list.uniq! list.sort! q = rand(1000) ans = if list.index(q).nil? then -1 else list.index(q) end assert_equal(binary_search(list, q), ans) end end end [/code] 정말 그렇더군요 -_-; 처음엔 지저분한 구현을 했다가, 이건 두번째로 작성한 버젼입니다..