Задача: пропущенный элемент в отсортированном массиве

Дан отсортированный по возрастанию массив целых чисел, все элементы которого уникальны. В массиве есть пропущенные элементы.
Необходимо найти k-й пропущенный элемент начиная с нулевого элемента массива.

Например: [4, 7, 9, 10], k = 1 -> Ответ 5. [4, 7, 9, 10], k = 3 -> Ответ 8 (пропущены 5, 6, 8)

Решение.

Линейный поиск. Первое решение, которое приходит в голову — линейный поиск. Последовательно циклом идти по массиву и для каждого элемента смотреть сколько элементов пропущенно. Например, для индекса i, число пропущенных элементов будет:

число пропущенных элементов для индекса i = arr[i] — arr[0] — i.

Давайте проверим это для массива [4, 7, 9, 10]. Для индекса i = 2:

число пропущенных = arr[2] — arr[0] — 2 = 9 — 4 — 2 = 3.

Т.е. для i = 2 (элемент 9), пропущенно 3 числа: 5, 6, 8.

Когда мы найдем первый элемент массива, для которого число пропущенных больше или равно k, значит искомый пропущенный элемент лежит между значениями arr[i — 1] и arr[i].

Например, для [4, 7, 9, 10] и k = 3 искомый индекс i = 2 (потому что число пропущенных равно 3 для индекса i = 2). Т.е. искомый пропущенный элемент лежит между arr[2–1] и arr[2], т.е. между 7 и 9.

Хорошо, мы вычислили, между какими значениями лежит искомое пропущенного число.

Как вычислить конкретно k-й пропущенный имея такой промежуток?

Можно применить такую формулу:

arr[i — 1] + k — (число пропущенных до arr[i — 1])

или

arr[i — 1] + k — (arr[i — 1] — arr[0] — (i — 1)) = arr[i — 1] + k — arr[i — 1] + arr[0] + i — 1 = arr[0] + k + (i — 1).

Реализация линейного поиска, который работает за O(n) по времени и O(1) по памяти:

    public int missingElement(int[] arr, int k) {
        int i = 0;
        for (; i < arr.length; i++) {
            int numerOfMissing = arr[i] - arr[0] - i;
            if (numerOfMissing >= k) {
                break;
            }
        }
        return arr[0] + k + i - 1;
    }

Можно ли еще улучшить решение?

Да можно. Можно применить бинарный поиск.

Бинарный поиск. Логика примерно такая же как и при линейном поиске, нам нужно на каждом шаге знать сколько пропущенных элементов для элемента массива arr[i]: arr[i] — arr[0] — i. И также будем искать промежуток между двумя элементами массива, между которыми лежит искомое число.

В бинарном поиске мы на каждом шаге вычисляем середину оставшейся области поиска mid = (left + right) / 2. Смотрим, сколько пропущенных элементов для arr[mid]: arr[mid] — arr[0] — mid.

Если число пропущенных элементов меньше k, то искомый промежуток справа. Если число пропущенных элементов больше или равно k, то слева.

Когда вывалимся из цикла, то искомый промежуток будет от right до right + 1. Вывалимся, когда right станет меньше left.

Тогда искомое значение будет вычисленно по той же формуле, что и при линейном поиске: arr[0] + k + (i — 1). Только i — 1 заменим на right: arr[0] + k + right.

Реализация, работает за O(log(n)) по времени и O(1) по памяти:

    public int missingElement(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int numerOfMissing = arr[mid] - arr[0] - mid;
            if (numerOfMissing < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return arr[0] + right + k;
    }