Можно ли использовать бинарный поиск, чтобы найти наиболее часто возникающее целое число в отсортированном массиве?

Question

Задача:

Учитывая, что отсортированный массив целых чисел находит наиболее часто встречающееся целое число. Если есть несколько целых чисел, удовлетворяющих этому условию, верните любой из них.

Мое основное решение:

сканирования через массив и отслеживать, сколько раз вы видели каждое целое число. Поскольку он отсортирован, вы знаете, что как только вы видите другое целое число, вы получили частоту предыдущего целого числа. Следите за тем, какое целое число имеет самую высокую частоту.

Это O (N) время, O (1) космическое решение.

Мне интересно, есть ли более эффективный алгоритм, который использует некоторую форму бинарного поиска. Это будет по-прежнему O (N) время, но оно должно быть быстрее для среднего случая.

Answer 1

Асимптотически (большой-о-мудрый), вы не можете использовать бинарный поиск, чтобы улучшить наихудший случай, по причинам, приведенным выше моих. Однако, вот некоторые идеи, которые могут или не помогут вам на практике.

Для каждого целого, двоичный поиск его последнего вхождения.Как только вы его найдете, вы знаете, сколько раз он появляется в массиве, и может соответствующим образом обновлять ваши счета. Затем продолжите поиск с позиции, которую вы нашли.

Это выгодно, если у вас есть только несколько элементов, которые повторяются много раз, например:

1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 

Потому что вы будете делать только 3 бинарных поисков. Однако, если у вас есть много различных элементов:

1 2 3 4 5 6 

Тогда вы будете делать O(n) бинарные поиски, в результате чего в O(n log n) сложности, так что хуже.

Это дает вам лучший лучший вариант и худший худший случай, чем ваш первоначальный алгоритм.

Можем ли мы сделать лучше? Мы могли бы улучшить худший случай, найдя последнее вхождение числа в позиции i следующим образом: посмотрите на 2i, затем на 4i и т. Д., Пока значение в этих позициях одинаково. Если их нет, посмотрите на (i + 2i)/2 т.д.

Для примера рассмотрим массив:

i 
1 2 3 4 5 6 7 ... 
1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 

Мы смотрим на 2i = 2, он имеет такое же значение. Мы смотрим на 4i = 4, то же значение. Мы смотрим на 8i = 8, различное значение. Мы возвращаемся к (4 + 8)/2 = 6. Различное значение. Назад к (4 + 6)/2 = 5. То же самое значение. Попробуйте (5 + 6)/2 = 5, то же значение. Мы больше не ищем, потому что наше окно имеет ширину 1, поэтому мы закончили. Продолжить поиск с позиции 6.

Это должно улучшить лучший случай, сохраняя наихудший случай как можно быстрее.

Асимптотически ничего не улучшается. Чтобы убедиться, что на практике это работает в среднем на практике, вам придется протестировать его.

Answer 2

Худший случай не может быть лучше, чем время O (n). Рассмотрим случай, когда каждый элемент существует один раз, за ​​исключением одного элемента, который существует дважды. Чтобы найти этот элемент, вам нужно будет посмотреть на каждый элемент массива, пока не найдете его. Это связано с тем, что знание значения любого элемента массива не дает вам никакой информации о местоположении дублирующего элемента, пока он не будет найден. Это контрастирует с бинарным поиском, где значение элемента массива позволяет исключить многие другие элементы.

Answer 3

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

Рассмотрим противник, который для первых n - 3 различных зондов в массиве n-элементов возвращает m для значения в индексе m. Теперь алгоритм знает, что массив выглядит

1 2 3 ... i-1 ??? i+1 ... j-1 ??? j+1 ... k-1 ??? k+1 ... n-2 n-1 n. 

В зависимости от того, что ??? s являются единственным правильным ответом может быть j-1 или j+1, поэтому алгоритм еще не сделано.

Этот пример включал массив, в котором было очень мало дубликатов. В факт, мы можем разработать алгоритм, который, если самый частый элемент происходит в k раз из n, использует O ((n/k) log k) зонды в массиве. Для j от ceil (log2 (n)) - 1 до 0, рассмотрите подмассив, состоящий из каждого (2 ** j) -го элемента. Остановитесь, если найдем дубликат. Стоимость равна O (n/k). Теперь для каждого элемента в подмассиве используйте бинарный поиск в , чтобы найти его протяженность (O (n/k) поиск в подмассивах размера O (k), для всего из O ((n/k) log k)) ,

Можно показать, что все алгоритмы имеют наихудший случай Omega ((n/k) log k), что делает его оптимальным в худшем случае до постоянных факторов.

Answer 4

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

Вот почему я думаю, что двоичный поиск не сработает: начните с массива: учитывая значение среднего элемента, у вас недостаточно информации для устранения нижней или верхней половины от поиска.

Однако мы можем сканировать массив в несколько проходов, каждый раз проверяя в два раза больше элементов. Когда мы находим два одинаковых элемента, сделаем один последний проход. Если никакие другие элементы не были повторены, вы нашли самый длинный элемент (даже не зная, сколько из этого элемента находится в отсортированном списке). В противном случае исследуйте две (или более) длинные последовательности, чтобы определить, какая из них самая длинная.

Рассмотрите отсортированный список.

Index 0 1 2 3 4 5 6 7 8 9 a b c d e f 
List 1 2 3 3 3 3 3 3 3 4 5 5 6 6 6 7 
Pass1 1 . . . . . . 3 . . . . . . . 7 
Pass2 1 . . 3 . . . 3 . . . 5 . . . 7 
Pass3 1 2 . 3 . x . 3 . 4 . 5 . 6 . 7 

После прохода 3, мы знаем, что бег 3-х должен быть не менее 5, в то время как самый длинный пробег любого другого числа не превосходит 3. Поэтому 3 является наиболее часто встречающимся номером в списке.

Используя правильные структуры данных и алгоритмы (используйте индексирование двоичного дерева), вы можете избежать чтения значений более одного раза. Вы также можете избежать чтения 3 (помечены как x в проходе 3), поскольку вы уже знаете его значение.

Это решение имеет время работы O(n/k), которое ухудшает до O(n) для k=1 для списка с n элементами и самым длинным пробегом k элементов. Для малых k наивное решение будет работать лучше благодаря более простой логике, структурам данных и большим хитам RAM cache.

Если необходимо определить частоту наиболее общего числа, это заняло бы O((n/k) log k), как указано Давида, чтобы найти первую и последнюю позицию самого длинного пробега чисел с помощью двоичного поиска на до n/k групп размера k.