Binary Search

어떤 사람들은 알고리즘이 명확하면 그의 구현은 간단하다고 말하지만, 실제로는 그렇지 않다. 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] 정말 그렇더군요 -_-; 처음엔 지저분한 구현을 했다가, 이건 두번째로 작성한 버젼입니다..

Similar Posts:

Comments 1