Нахождение пропущенного номера с помощью бинарного поиска

Идея состоит в том, чтобы решить более простую проблему:

Отсутствует значение в диапазоне [minVal, X] или (X, maxVal).
Если вы знаете это, вы можете переместить X и проверить еще раз.

Например, у вас есть 3, 4, 1, 5 (2 отсутствует).
Вы знаете, что minVal = 1, maxVal = 5.

1. Range = [1, 5], X = 3, должно быть 3 целых числа в диапазоне [1, 3] и 2 в диапазоне [4, 5]. Есть только 2 в диапазоне [1, 3], поэтому вы смотрите в диапазоне [1, 3]
2. Range = [1, 3], X = 2. В диапазоне [1, 2] есть только 1 значение, поэтому вы смотрите в диапазоне [1, 2]
3. Range = [1, 2], X = 1. В диапазоне [2, 2] нет значений, так что это ваш ответ.

РЕДАКТИРОВАТЬ: Некоторые псевдо-C ++ код:

minVal = 1, maxVal = 5; //choose correct values
while(minVal < maxVal){
int X = (minVal + maxVal) / 2
int leftNumber = how much in range [minVal, X]
int rightNumber = how much in range [X + 1, maxVal]
if(leftNumber < (X - minVal + 1))maxVal = X
else minVal = X + 1
}

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

• unsigned long next_number (void) читает число из файла и возвращает его. При повторном вызове возвращается следующий номер в файле и т. Д. Поведение при обнаружении конца файла не определено.

• int numbers_left (void) возвращает истинное значение, если доступно больше чисел для чтения с использованием next_number(), false, если достигнут конец файла.

• void return_to_start (void) перематывает позицию чтения в начало файла, чтобы следующий вызов next_number() возвращает первое число в файле.

Я также предполагаю, что unsigned long имеет ширину не менее 32 бит, как требуется для соответствия реализациям ANSI C; современные программисты C могут предпочесть использовать uint32_t от stdint.h вместо.

Учитывая эти предположения, вот решение:

unsigned long count_numbers_in_range (unsigned long min, unsigned long max) {
unsigned long count = 0;

return_to_start();

while ( numbers_left() ) {
unsigned long num = next_number();
if ( num >= min && num <= max ) {
count++;
}
}
return count;
}

unsigned long find_missing_number (void) {
unsigned long min = 0, max = 0xFFFFFFFF;

while ( min < max ) {
unsigned long midpoint = min + (max - min) / 2;
unsigned long count = count_numbers_in_range( min, midpoint );

if ( count < midpoint - min + 1 ) {
max = midpoint;  // at least one missing number below midpoint
} else {
min = midpoint;  // no missing numbers below midpoint, must be above
}
}
return min;
}

Обратите внимание на одну деталь: min + (max - min) / 2 это безопасный способ рассчитать среднее min а также max; это не даст ложных результатов из-за переполненный промежуточные значения, такие как, казалось бы, проще (min + max) / 2 может быть.

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

Наконец, было бы легко оптимизировать этот код, например, вернувшись, как только count равно нулю, считая числа в и то и другое половин диапазона за один проход и выбирая тот, у которого больше пропущенных чисел, или даже путем расширения двоичного поиска до N-поиск некоторых N > 2, чтобы уменьшить количество проходов. Однако, чтобы сделать пример кода как можно более простым, я оставил такие оптимизации без изменений. Если хотите, вы можете, скажем, попробовать изменить код так, чтобы он требовал не более восьми проходов по файлу вместо текущих 32. (Подсказка: используйте массив из 16 элементов.)

На самом деле, если у нас есть диапазон целых чисел от а до б. Образец: [a..b].
И в этом диапазоне у нас есть целые числа b-a. Это означает, что отсутствует только один.
И если отсутствует только один, мы можем вычислить результат, используя только один цикл.
Сначала мы можем вычислить сумму всех целых чисел в диапазоне [a..b], которая равна:

sum = (a + b) * (b - a + 1) / 2

Затем мы вычисляем сумму всех целых чисел в нашей последовательности:

long sum1 = 0;
for (int i = 0; i < b - a; i++)
sum1 += arr[i];

Тогда мы можем найти отсутствующий элемент как разность этих двух сумм:

длинный результат = sum1 — сумма;

когда вы увидели 2 ^ 31 нулей или единиц в месте с i-й цифрой, тогда в вашем ответе будет один или ноль на i-м месте. (Пример: 2 ^ 31 в 5-й двоичной позиции означает, что ответ имеет ноль в 5-й двоичной позиции.

Первый набросок кода c:

uint32_t binaryHistogram[32], *list4BILLION, answer, placesChecked[32];
uint64_t limit = 4294967296;
uint32_t halfLimit = 4294967296/2;
int i, j, done

//General method to point to list since this detail is not important to the question.
list4BILLION = 0000000000h;//Initialize array to zero. This array represents the number of 1s seen as you parse through the list
for(i=0;i<limit;i++)
{
binaryHistogram[i] = 0;
}

//Only sum up for first half of the 4 billion numbers
for(i=0;i<halfLimit;i++)
{
for(j=0;j<32;j++)
{
binaryHistogram[j] += ((*list4BILLION) >> j);
}
}

//Check each ith digit to see if all halfLimit values have been parsed
for(i=halfLimit;i<limit;i++)
{
for(j=0;j<32;j++)
{
done = 1;   //Dont need to continue to the end if placesChecked are all
if(placesChecked[j] != 0) //Dont need to pass through the whole list
{
done = 0; //
binaryHistogram[j] += ((*list4BILLION) >> j);
if((binaryHistogram[j] > halfLimit)||(i - binaryHistogram[j] == halfLimit))
{
answer += (1 << j);
placesChecked[j] = 1;
}
}
}
}