Binary Search

Tags:

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

Comments

One response to “Binary Search”

  1. 공성식 Avatar
    공성식

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *