поиск значения в несортированном массиве в O (log n)

Question

Мой друг получил вопрос в тесте, вопрос был:

Вы получаете несортированный массив с целочисленными значениями в виде пар и 1 значением, например, одним:

[1,1,5,5,2,2,4,4,7,12,12,8,8]

Вывод: 7

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

Так как это можно сделать в O (log n) для этого несортированного массива?

Answer 1

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

1. Разбейте массив на то, что должен иметь 2n + 1 элементов следующим образом: <n elements> <1 element> <n elements>:
2. Сравните средний элемент с последним элементом первой части и первым элементом второй части :
   • если оно не равно обоим , найден отдельный элемент
   • в противном случае добавить средний элемент к части с тем же элементом (если он равен последнему элементу первой части, добавить его к первой части, в противном случае добавить его в качестве первого элемента ко второй части)
3. Повторите шаги с частью , имеющей нечетное количество элементов

Answer 2

Рассмотрим вспомогательный массив, сформированный путем взятия каждого другого числа и присвоения 0, если оно равно следующему, и 1 в противном случае.

[1,1,5,5,2,2,4,4,7,12,12,8,8]
[0,  0,  0,  0,  1,   1   ]

Этот вспомогательный массив четко отсортирован, и первый можно найти с помощью бинарного поиска.

Конечно, массив не должен быть создан явно, так как это займет O (N).

Answer 3

Если достаточно заметить, что все пары слева от синглтона имеют четные / нечетные индексы, а справа - нечетные / четные.

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

Это верно только в том случае, если соседние пары различны или если серии равных пар никогда не превышают длину O (1). Например, с одним 7 среди всех пар 8, только линейный поиск можно сделать.