pesquisa_binaria.lua

pesquisa_binaria.lua

local function pesquisa_binaria(lista, item)
  local interacao = 1
  local baixo = 1
  local alto = #lista

  while baixo <= alto do
    interacao = interacao + 1
    local meio = math.floor(#lista / 2)
    local chute = lista[meio]

    if chute == item then
      return chute, interacao
    end

    if chute > item then
      alto = meio - 1
    else
      baixo = meio + 1
    end
  end

  return nil, interacao
end

local function main()
  local lista = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
  local item = 5
  local chute, interacao = pesquisa_binaria(lista, item)
  print('Item ' .. chute .. ' encontrado na interação ' .. interacao)
end

main()