В настоящее время я готовлюсь к экзамену по введению в алгоритмы и столкнулся с вопросом, который не могу решить на самом деле. Вопрос в следующем: у вас есть массив из n целых чисел, первые m элементов четные, и остальные элементы странные. Вам необходимо написать алгоритм, который находит значение m (находит индекс последнего четного числа) и имеет временную сложность O (log m).
Я думал о том, чтобы сделать что-то похожее на бинарный поиск и просто переместиться влево, если он нечетный, и переместиться вправо, если даже, пока не найду индекс, который является четным, а его следующий нечетный, но эта вещь будет работать в O (log n) и не O (log m).