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

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

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

EDIT: Спасибо всем за ваш замечательный ответ и комментарии! Самый важный урок, который я от него решаю: Двоичный поиск применяется не только к отсортированному массиву!

6 ответов

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

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

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


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

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

Damien


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


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

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

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

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

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

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

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

Каждый раунд удвоит пространство поиска и что оно.

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


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

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


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

  • По мере продвижения по списку целых чисел вычислите сумму.
  • В конце вычислим сумму так, как если бы все целые числа присутствовали по формуле N * (N + 1)/2
  • Извлеките сумму в (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. QED

licensed under cc by-sa 3.0 with attribution.