Теоретическая нижняя оценка нахождения количества вхождений целого числа целевого числа в отсортированном массиве

Question

Учитывая отсортированный массив целых чисел и целевого целого числа, найдите количество вхождений целого числа целевого значения.

Общеизвестно, что двоичный поиск имеет временную сложность $ o (\ lg n) $ где $ n$ - это размер массива. Например, учитывая массив $ [1,2,3,3,4,5] $ и цель $ 3,$ Алгоритм должен вернуться $ 2 $ Поскольку есть два копии $ 3 $ в массиве,

Вопрос: Есть ли у более быстрых алгоритмов, которые имеют временную сложность меньше, чем $ O (\ lg n)? $ в противном случае, есть ли доказательство, чтобы доказать, что $ \ Omega (\ lg n) $ - это теоретический нижний?

Answer 1

Проблема требует $ \ Omega (\ log n) $ Доступ к памяти, даже если вам обещают, что целевое целое число появляется максимум. Вы можете доказать это, используя корреспонденцию противника.

сказать, что цель равна нулю. Если первый доступ к массиву осталось от центра, ответьте $ - 1 $ , и мысленно устанавливать элементы влево, чтобы быть $ - 2, -3, \ ldots $ . Если первый доступ справа от центра, ответьте $ + 1 $ и мысленно устанавливать элементы вправо на $ 2 , 3, \ ldots $ .

Предположим, что первый доступ был прав в центре, скажем, позиция $ i $ и рассмотрим второй доступ. Если это это справа от первого доступа, то вы уже знаете, что ответить. В противном случае есть два случая. Если доступная позиция $ j $ меньше, чем $ i / 2 $ , ответа $ - 1 $ (и заполните элементы слева). Если бы это было больше, чем $ i / 2 $ , ответьте на $ + 1/2 $ (и заполните Элементы вправо до положения $ i $ ).

Продолжается таким образом, на каждом этапе на несколько позиций, которые могут содержать целевой элемент, прилагается к снижению вдвое на каждом этапе. Наконец, когда только один элемент по-прежнему на карту, не запрашивая его, алгоритм не может точно знать, содержит ли массив целевой элемент или нет. Это требует $ \ log_2 n $ Шаги для достижения этого шага.

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

Answer 2

Есть $ n $ Возможные ответы.Каждое сравнение дает вам максимум одной информации.Вам нужно хотя бы $ \ lg n $ Биты информации, чтобы описать ответ, поэтому вам понадобится как минимум $ \lg n $ сравнения.