Алгоритм вопроса. Я не понимаю предложение цитируется. Пожалуйста, помогите мне

Question

Вопрос от Programming Pearls, 2-е издание:

Учитывая последовательный файл, содержащий 4 300 000 000 32-разрядных целых чисел, как найти тот, который появляется по крайней мере дважды?

Решение, представленное в книге:

Двоичный поиск находит элемент, который встречается как минимум дважды, путем рекурсивного поиска в подинтервала, который содержит более половины целых чисел. Мое оригинальное решение не гарантировало, что число целых чисел уменьшается в каждой итерации вдвое, поэтому время выполнения его худших случаев log ₂ n было пропорционально n & middot; log п . Джим Сэкс уменьшил это до линейного времени, заметив, что поиск может избежать переноса слишком большого количества дубликатов.

Когда его поиск знает, что дубликат должен быть в текущем диапазоне из m целых чисел, он будет хранить только m + 1 целые числа на текущей рабочей ленте;

Если бы на ленту ушло больше целых чисел, его программа их отбрасывает Хотя его метод часто игнорирует входные переменные, его стратегия достаточно консервативна, чтобы обеспечить поиск хотя бы одного дубликата.

---

Выше содержание книги. Я не понимаю приведенные предложения. Как именно это может быть реализовано? Я имею в виду, как он может знать, что «дубликат должен быть в текущем диапазоне m целых чисел»?

Спасибо за вашу помощь!

Answer 1

2 ^ 32 = 4 294 967 296. У вас есть файл с 4 300 000 000 целых чисел, гарантирующий дубликаты.

1. Найдите центральное число, оно должно быть 2 ^ 31 = 2147483648. Если оно меньше, скорее всего, дубликаты находятся во второй половине. Если нет, дубликаты произошли в первой половине.

2. Снова найдите центральный номер, он должен 2 ^ 30 = 1073741824 ...

Повторяйте, пока не найдете дубликат.

Answer 2

Я думаю, что это относится к принципу квадратного отверстия: если разница между минимальным и максимальным элементом в наборе меньше, чем количество элементов в наборе, должен быть дубликат.

И вы можетепроверьте это, когда вы создаете свои подмножества, и прекратите их создавать, как только вы убедитесь, что в этом подмножестве должен быть дубликат.

Answer 3

Ничего себе.Я думаю, что эта книга может быть немного старой.Это основная проблема бинарного поиска.

И я думаю, что книга немного неловкая.Может быть, попробуйте википедию

http://en.wikipedia.org/wiki/Binary_search_algorithm