Лучший способ найти небольшую группу чисел в большой группе

Question

Я очень далек от математики, но хотел бы получить совет от знающих людей.

Представьте себе большую группу чисел от 1 до 1 экзабайт.
В этой группе мы должны найти небольшую скрытую группу из 1000 чисел (без пробелов) с начальной точкой от 1 петабайт, скажем так.
Я понимаю, что группа большая и, вероятно, нет способа найти координаты этой небольшой группы.
Но ..
Как мне нужно пробовать сканировать большую группу, чтобы получить хотя бы один номер из небольшой группы?
Мне ясно, что тест случайных чисел - это худший способ.
Остается еще один вариант.
Возьмите 1 Эксабайт и разделить это число каждый раз, постепенно и для тестирования Groupe координат каждый раз:

• 1 эксабайт/3 -> мы будем иметь 3 координаты, чтобы проверить, добавив результат 1 каждый раз.
• 1 экзабайт/4 -> мы проверим 4 координаты, добавив результат в 1 каждый раз.
• ....

Есть ли лучший способ? Может быть, псевдокод или код в C?

P.S. Я не могу объяснить проблему подробно.
Я еще не упомянул, что могу увеличить размер небольшой группы. От 1000 до 1000000 (например), но его сложнее вычислить для компьютера. И с вашей помощью: случайное решение + увеличение небольшой группы, похоже, сейчас является хорошим выбором.
** Спасибо всем за ваши идеи **

Answer 1

Вы не упоминаете, если отсортирован или нет, поэтому для любой случай:

• Проверить каждый n-й, где n = 1000 или любой другой размер «маленькая скрытая группа».
• При обнаружении проверьте любую сторону (любое количество в сторону в диапазоне [1, n]).
• Если необходимо, проверьте остальную часть диапазона до отказа.
• Если это неверно (в любой точке), проверьте другую сторону.
• Если другая сторона неправильно, проверьте следующее n-й

например Псевдо:

for i in range(0,N/n){ 
    if i in small_set{ 
     left_limit = test(i, left) 
     right_limit = test(i, right) 
     if (right_limit - left_limit == n) return left_limit 
    } 
} 

def test(position, direction) 
    move = 1 
    if (direction == left) move = move *-1 
    while (position in small_set) position += move 
    return position 

я не требование это наиболее эффективным, но это, конечно, просто, и наиболее эффективным я могу думать быстро.

Кроме того, вы неправильно в высказывании:

...тест на случайное число является наихудшим способом

В среднем, я считаю, что наименее эффективным методом будет последовательный тест. Если первое число не находится в группе, то это совершенно бессмысленно, проверяя следующий n-1.

Если это упорядоченное множество, а небольшая группа последовательны, то мы можем сделать точно так же, как и выше, за исключением того, нет необходимости проверять весь диапазон, только i и i + n - 1, где i является позиция первый элемент из меньшего набора в большем наборе.