Справка по бинарному поиску "Programming Pearls"

Question

Я просто не могу понять, как это будет работать.

Вопрос:
Если задан последовательный файл, содержащий не более четырех миллиардов 32-битных целых чисел в случайном порядке, найдите 32-разрядное целое число, которого нет в файле (и должно отсутствовать хотя бы одно пропущенное)

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

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

Итак, разделив файл снова и снова (бинарный поиск), как это приведет меня к отсутствующему 32-битному целому числу?

Answer 1

После каждого прохода ваш следующий проход будет в меньшем из двух составленных вами списков.

В какой-то момент вы ДОЛЖНЫ встретить пустой список, и это определит ваш номер. Например, давайте просто использовать 3-битные числа.

000
001
110
100
111

после первого прохода имеем

000
001

110
100
111

Затем мы смотрим на 2-й бит в первом списке, потому что он меньше (или равен) второму. Мы бы разбили их на

000
001

empty list

обратите внимание, что файл, начинающийся с 01, пуст, это означает, что нет чисел, начинающихся с 01, поэтому отсутствуют 010 и 011.

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

Answer 2

В конце концов, если вы продолжите расщепление, у вас будет (максимум) 4 миллиарда файлов, каждый из которых содержит одно целое число. Теоретически, вы будете «знать», какой из них отсутствует, потому что для него не будет файла.

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

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