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

  1. 공성식 wrote:

    완전히 모범답안을 작성하신 것 같네요.

    루비나 파이썬 같은 언어에서는 별것 아닌 것이 C나 자바 같은 언어에서는 골칫거리인 경우가 많은 것 같아요.
    특히 검색엔진 같은 경우 워낙에 큰 데이터를 다루다보니 예전에 못 보던 버그들이 나타나곤 하죠.
    (left + right) 은 자바 같은 언어에선 integer overflow를 내기 딱 좋은 경우라…
    비트쉬프트를 하지 않고 2로 나누기를 하면 엉뚱한 결과가 나오기 십상이죠.

    Rubyist들은 참 축복받은 프로그래머들이죠…:-)

    Posted 15 Jun 2006 at 2:10 am

Post a Comment

Your email is never published nor shared.