Помощь в программировании бинарного поиска Pearls

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

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

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

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

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


algorithm programming-pearls
person bbbb    schedule 16.02.2011    source источник

Ответы (2)


arrow_upward
12
arrow_downward

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

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

000
001
110
100
111

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

000
001

110
100
111

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

000
001

empty list

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

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

person WuHoUnited    schedule 16.02.2011
comment
А 101? Не должно ли это тоже отсутствовать - person bbbb; 16.02.2011
comment
В вашем вопросе сказано найти A число, а не найти ALL числа. Вот почему этот метод работает. - person WuHoUnited; 16.02.2011
comment
О, я вижу, я думал, что он выплюнет все цифры, спасибо! - person bbbb; 16.02.2011
comment
@WuHoUnited Затем мы смотрим на 2-й бит в первом списке, потому что он меньше (или равен) второму ... меньше или равен какому второму? И какая будет большая сложность O? O(lgn) ? - person Geek; 07.09.2012
comment
@Geek В этом предложении первый список относится к 000, 001 (второй список будет 110, 100, 111). Под меньшим я подразумеваю, что в нем меньше элементов. Большая сложность O (n) зависит от того, что вы хотите быть n (является ли n в этом случае 32 битами или это 2 ^ 32 возможных числа или это четыре миллиарда выбранных чисел) - person WuHoUnited; 08.09.2012

arrow_upward
0
arrow_downward

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

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

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

person Scott M.    schedule 16.02.2011