Найти недостающее 32-битное целое число среди несортированного массива, содержащего не более 4 миллиардов целых

Question

Это проблема , описанная в Programming pearls. Я не могу понять метод бинарного поиска, описанный автором. Может кто-нибудь поможет уточнить? Спасибо.

EDIT: Я могу понять бинарный поиск в целом. Я просто не могу понять, как применить бинарный поиск в этом особом случае. Как определить, находится ли пропущенное число в каком-то диапазоне или нет, чтобы мы могли выбрать другое. Английский не мой родной язык, поэтому я не могу понять автора. Итак, используйте простой английский, пожалуйста:)

РЕДАКТИРОВАТЬ: Спасибо всем за ваш отличный ответ и комментарии! Самый важный урок, который я извлек из решения этого вопроса, - Бинарный поиск применяется не только к отсортированному массиву !

Answer 1

Более подробная информация о этом веб-сайте . Цитируется оттуда:

"Полезно рассматривать этот двоичный поиск в терминах двадцати битов, представляющих каждое целое число. На первом проходе алгоритма мы читаем (не более) миллиона входных целых чисел и записываем те, у которых начальный нулевой бит одна лента и те, у которых один ведущий бит переходит на другую ленту. Одна из этих двух лент содержит не более 500 000 целых чисел, поэтому мы затем используем эту ленту в качестве текущего входа и повторяем процесс проверки, но на этот раз для второго бита. исходная входная лента содержит N элементов, первый проход будет читать N целых чисел, второй проход не более N / 2, третий проход не более N / 4 и т. д., поэтому общее время выполнения пропорционально N. Пропущенное целое число может быть найден путем сортировки на ленте и последующего сканирования, но для этого потребуется время, пропорциональное N log N. "

Как видите, это разновидность алгоритма бинарного поиска: разделите задачу на две части и решите задачу для одной из меньших частей.

Answer 2

Это в основном тот же вопрос, что и этот вопрос . Тот же подход работает здесь для случая достаточного объема памяти, чтобы получить сложность O (N). В основном просто рекурсивно попробуйте поместить каждое целое число в правильное местоположение и посмотреть, что не имеет правильного значения.

Answer 3

Если учесть числа в диапазоне от 1 до N; половина из них больше чем N / 2 и половина из них меньше чем N / 2

Если значение больше N / 2, MSB будет установлен в единицу; MSB = 0 для меньших.

Разбейте весь набор на основе MSB, который даст вам два набора: набор чисел, меньший, чем N / 2, и набор чисел, больший, чем N / 2

Раздел меньшего размера содержит отсутствующий элемент.

На следующем шаге используйте следующий MSB.

1. Если меньший набор был меньше N / 2, половина из них меньше N / 4 (2-й MSB = 0), а другая половина больше, чем N / 4 (2-й MSB = 1)

2. Если меньший набор был больше, чем N / 2, половина из них меньше, чем N / 2 + N / 4 (2-й MSB = 0), а другая половина больше, чем N / 2 + N / 4 ( 2-й разряд MSB = 1)

Каждый раунд будет вдвое уменьшать пространство поиска, и все.

 Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)

Answer 4

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

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

Answer 5

Я полагаю, что автор понимает, что вы выбираете середину текущего диапазона целых чисел и готовите два выходных файла. Когда вы читаете ввод, все, что выше средней точки, переходит в один файл, а все, что ниже средней точки, переходит в другой.

По окончании вы выбираете, какой из файлов меньше, а затем повторяете операцию, используя [нижняя граница, средняя точка] или (средняя точка, верхняя граница] в качестве нового диапазона, пока файл и диапазон не станут достаточно маленькими переключиться на растровый шаблон (или один из ваших выходных файлов пуст).

Дэмиен

Answer 6

Ну, это о файле, который содержит все 4 миллиарда целых, кроме одного! Это подвох в этом случае.

1. По мере продвижения по списку целых чисел вычисляйте сумму.
2. В конце вычислите сумму, как если бы присутствовали все целые числа, используя формулу N * (N + 1) / 2
3. Извлеките сумму в (1) из суммы, которую вы вычислили в (2). Это недостающее целое число.

Пример: Предположим, у нас есть следующая последовательность: 9 3 2 8 4 10 6 1 7 (от 1 до 10 с 5 пропущенными). Последовательно добавляя целые числа, мы получаем 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50. Сумма всех целых чисел от 1 до 10 будет 10 * (10 + 1) / 2 = 55 Поэтому отсутствующее целое число равно 55 - 50 = 5. КЭД