Поиск элемента, который встречается чаще, чем другой

Question

Я хочу алгоритм, который вычисляет, какой элемент среди двух появляется чаще, чем другой в отсортированном массиве. Массив будет иметь только два типа элементов.

Пример: $ aaaaaabbb $

Здесь $ a> b $.

Я должен найти постоянный алгоритм времени. Является ли это возможным? Единственное, что я мог придумать, это использование стека. Нажмите все $ $ A $ и нанесите их с $ b $. Но это требует операций $ O (n) $. Есть лучшие подходы? Нужен подсказка (без решения).

Answer 1

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

Если средний номер составляет $ a $, то, поскольку массив отсортирован, $ a $ появляется более чем $ b $, а в остальном $ b $ делает.

Тем не менее, это не совсем так, что это постоянный алгоритм времени, поскольку он предполагает, что вы можете вычислить длину массива в постоянное время.

Это невозможно в стандартной TM и даже в модели RAM. Требуется как минимум $ O ( log n) $ операции в последнем, где $ n $ - это продолжительность массива.