CodeKata dois – Pesquisa binária

28ago07

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:

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

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
Anúncios


No Responses Yet to “CodeKata dois – Pesquisa binária”

  1. Deixe um comentário

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s


%d blogueiros gostam disto: