Keep Learning Conhecimento nunca é o bastante

CodeKata dois – Pesquisa binária

Há algum tempo falei do blog CodeKata, que contém exercícios para praticar programação. O primeiro exercício não é prático, então não fiz um post sobre ele, embora seja bem interessante. Já o segundo exercício pede que sejam escritos alguns algoritmos para pesquisa binária em um vetor.

Consegui desenvolver o algoritmo iterativo em Ruby, o próximo passo (quando houver tempo hábil) é desenvolver uma versão recursiva.

Veja o código abaixo:

[sourcecode language='ruby']
require ‘test/unit’

class CodeKataTwo < Test::Unit::TestCase
def chop(numero, array)
min = 0
max = array.length
max -= 1

arr_procura = array

while true
if arr_procura.length == 0
return -1
end
if arr_procura.length == 1
if arr_procura[0] == numero
return min
else
return -1
end
end

mid = (arr_procura.length) / 2

if numero < arr_procura[mid]
max -= mid
else
min += mid
end
arr_procura = array[(min..max)]
end
end

def test_chop
assert_equal(-1, chop(3, []))
assert_equal(-1, chop(3, [1]))
assert_equal(0, chop(1, [1]))
#
assert_equal(0, chop(1, [1, 3, 5]))
assert_equal(1, chop(3, [1, 3, 5]))
assert_equal(2, chop(5, [1, 3, 5]))
assert_equal(-1, chop(0, [1, 3, 5]))
assert_equal(-1, chop(2, [1, 3, 5]))
assert_equal(-1, chop(4, [1, 3, 5]))
assert_equal(-1, chop(6, [1, 3, 5]))
#
assert_equal(0, chop(1, [1, 3, 5, 7]))
assert_equal(1, chop(3, [1, 3, 5, 7]))
assert_equal(2, chop(5, [1, 3, 5, 7]))
assert_equal(3, chop(7, [1, 3, 5, 7]))
assert_equal(-1, chop(0, [1, 3, 5, 7]))
assert_equal(-1, chop(2, [1, 3, 5, 7]))
assert_equal(-1, chop(4, [1, 3, 5, 7]))
assert_equal(-1, chop(6, [1, 3, 5, 7]))
assert_equal(-1, chop(8, [1, 3, 5, 7]))
end

end
[/sourcecode]

Salve o código num arquivo (por exemplo, bin.rb) e rode o programa:

C:>ruby bin.rb
Loaded suite bin
Started
.
Finished in 0.0 seconds.

1 tests, 19 assertions, 0 failures, 0 errors