Passion is like genius; a miracle.

어떤 사람들은 알고리즘이 명확하면 그의 구현은 간단하다고 말하지만, 실제로는 그렇지 않다. 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

정말 그렇더군요 -_-;
처음엔 지저분한 구현을 했다가, 이건 두번째로 작성한 버젼입니다..