Найдите пропущенное число в несортированном массиве, используя числа «разделяй и властвуй» и срединные

Question

Допустим, у нас есть несортированный массив с номерами от 0 до n (n = 2 ^ k - 1, k - целое число), кроме единицы. Моя цель - найти пропущенное число.

Мне известен метод XOR или метод sum. Тем не менее, я должен использовать стратегию «разделяй и властвуй» и кое-что, что связано со средним числом массива.

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

Однако я не думаю, что это работает. Какие изменения вы предлагаете?

Answer 1

Вот еще одна идея.

Метод «разделяй и властвуй»

1. Пусть недостающее число, m, будет n / 2.
2. Подсчитайте числа меньше чем m.
3. Если число меньше, чем m
   1. Тогда мы знаем, что пропущенное число меньше, чем m.
   2. Иначе, отсутствующее число больше или равно m.

Продолжайте делать это, пока не найдете отсутствующее число.

Python реализация:

def missingNumber(nums):

    lo, hi = 0, len(nums)

    while lo < hi:
        m = (lo + hi + 1) // 2
        smaller = sum(x < m for x in nums)

        if smaller < m:
            hi = m - 1
        else:
            lo = m

    return lo

Answer 2

Вы можете разделить массив на 2 массива, один со значениями меньше, другой со значениями, превышающими медиану. Вы можете проверить, сколько элементов должно быть в обоих этих массивах, основываясь на предположении о вашем первом предложении.
Тогда один из массивов должен быть на 1 меньше, чем предполагалось. Поэтому вы можете искать там.
В таком случае ваше условие выхода будет выглядеть примерно так, что массив должен связываться со всеми элементами между x и x (поэтому просто x), но он пуст. Следовательно, х - недостающий элемент.