Find two skipped numbers in a natural sequence

generate_source_data.rb

# Run it only with ruby 1.9.

range = (1..(ARGV[0] || 10).to_i)

@g = Random.new
def gen_skips(n, range, ready = [])
  return ready if ready.size == n
  gen_skips(n, range, ready.push(@g.rand(range)).uniq)
end

skips = gen_skips(2, range).sort
fn = 'data.txt'

puts "Generating...\n\n"
step = [range.first, (range.last - range.first + 1)/100].max.to_i

File.open(fn, 'w') do |f|
  range.each do |n|
    print '*' if n % step == 0
    f.puts(n) unless skips.include?(n)
  end
end

puts "\n\nGenerated #{fn} with numbers from #{range.first} to #{range.last} with #{skips.join(', ')} skipped."

Как терминировать мой бинарный поиск, я уже понял, это оказалось совсем несложно.
Когда будет свободное время в ближайшие день-два, допишу.
Спасибо Андрею за конструктивную часть критики в этом направлении.

Все получилось, код здесь:
https://gist.github.com/2908925

типичные средние результаты:

partition algorithm	10,000	1,000,000
"5/8" partition	0.004767s	0.009469s
"1/2" partition	0.004643s	0.009897s

Напомню, что все корректно работает для любого количества пропусков в любых конфигурациях, включая пропуски нескольких чисел подряд и пропуски с начала ряда (это касается функции check_range_pos(), подробности см. ниже).

Дима, а можно проверить это на вашем компе? Сравнить интересно, на правах "вне конкурса", конечно :)

И еще: поскольку для правильного кода потребовалась функция для подсчета числа байт-позиций в заданном целочисленном интервале, захотелось уже и реализовать алгоритм честного деления "1/2". Функция check_range_pos() - деление "5/8" (по байтам), check_range_num() - деление "1/2" (по числам). Эта функция не столь универсальна, т.к. будет глючить в случае нескольких пропущенных чисел подряд.
Что интересно, что их производителдьность практически совпадает, иногда даже "5/8" работает быстрее чем "1/2". Это скорее всего связано с тем, что "1/2" требует больше операций, возможно теоретическая разница проявится на бОльших количествах.

Я гонял тесты у себя дома, там завтра и запущу ваш. Это очень интересно. Спасибо вам большое. Решение прочитаю точно.

Деление по числам, в виду не универсальности, не так интересно, особенно с учётом того, что оно не столь однозначно лучше.

Спасибо!
С нетерпением жду результата... :)

Не совсем понимаю, как вам удаётся обойтись ещё и без знания количества пропущенных чисел, а код лёгким к чтению не назовёшь.

Но результаты вполне впечатляют, так что, завтра чтобы понять, буду рефакторить =)

Никакой уличной магии. :)
Фишка в том что пропуски сканятся только в парах ближайших соседей с любым отклонением от последовательного порядка, типа [3;5], [2;7].
Ну и начало вычисляется отдельно, учитывая что это не обязательно 1.
За код "с душком" прошу прощения, я пока писал на это не обращал внимания, а теперь отлежаться должно для рефакторинга, так что заранее благодарю.

Да я всё понимаю - я ж не говорю, что вы плохо написали, я говорю, что так сразу не прочитаешь =) Не за что извиняться.

Обновлённая производительность:

                                            10000    1000000        100000000
=====================================================================================
  python andy128kpython.py                   0.046      1.188       couldn't wait
  sbcl --script andy128k.lisp                0.073      0.675       heap exchausted
  ruby bronislav.rb                          0.148      0.761       couldn't wait
  ruby zhck.rb                               0.149      0.739       couldn't wait
  ruby dmitriy-kiriyenko.rb                  0.152      1.139       couldn't wait
* ruby raven29_cool.rb                       0.145      0.158       0.161
  ruby raven29.rb                            1.885   3:34.870       not measured
  mysql test_num < dmitriy-kiriyenko.sql  1:13.460   not measured   not measured