Почему не работает этот двоичный поисковый код Ruby? - PullRequest
Новая
       13

Почему не работает этот двоичный поисковый код Ruby?

0 голосов
/ 21 марта 2011

У меня есть такой код 

def search(begins, ends)
  puts "Searching for  #{begins}- #{ends}"
  temp = ((begins + ends) / 2).to_i
  if is_valid? temp
    if (ends - begins).abs < 3 # the result is between a and 2 digits than b
      return temp # recursion ends
    else
      search(begins, temp)
    end
  else
    search(temp, ends)
  end
end

Существует диапазон чисел от 0 до 10000000, которые передают функцию is_valid.Я хочу найти первый и последний элемент, которые передают эту функцию, используя этот код, но он не работает, он даже не близок. Он идет в бесконечном цикле, и здесь несколько строк вывода

1 Ответ

0 голосов
/ 21 марта 2011

Посмотрите на код, который вы написали: ничто в нем не приведет к тому, что ends окажется где-то около 3745311 в точке, на которую вы претендуете.3745311 + 7490622 - это 11235933, который, деленный на 2, дает нам 5617966, как вы видите.5617966 - 3745311 намного больше 3, поэтому он вычисляет 3745311 + 5617966, что составляет 4681638 - опять же, как вы видите.

Я думаю, возможно, вы хотели использовать ends / 2 вместо (begins + ends) / 2.Это может привести к 3745311 в точке, которую вы ожидаете.

...