Как найти элемент в отсортированном по m массиве, где остаток массива равен нулю, а m не задано

Question

Дан массив с n элементами. Первые m элементов в массиве отсортированы (без дубликатов) и отличаются от нуля. Остальная часть массива - нули.

Следует отметить, что m неизвестно - это может быть что угодно, но известно, что n >> m .

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

. Тривиальным ответом будет сканирование массива до тех пор, пока следующий элемент не равен нулю, с O (m ) временная сложность, или просто модифицированная версия «Бинарного поиска», которая потребует O (logn) временной сложности. Помимо этих двух решений - я понятия не имею. Намекнули, что мы можем найти x в O (log m) сложности времени, найдя m в O (logm) времени Тогда я мог бы выполнить бинарный поиск по первым m элементам ... но в противном случае я понятия не имею!

Answer 1

Вы можете найти m в O(log m) времени следующим образом (учитывая, что первые m элементы не содержат 0).

i = 1
while A[i] != 0 do
  i = 2*i
return i

Это дает Вы - верхняя граница m, которая не более 2m (что означает m <= i <= 2m). Все, что вам нужно сделать, это двоичный поиск по i первым элементам вашего массива, чтобы найти x.

Каждая операция может быть выполнена за O(log m) время, поэтому общая сложность составляет O(log m).