Здравствуйте, cppguard, Вы писали:

C>Здравствуйте, landerhigh, Вы писали:

L>>Нет, там можно (и нужно) получить именно O(N+log(M))
L>>Имхо это может быть сложно увидеть сразу, но при попытке реализовать алгоритм станет очевидно.

C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.

Дело в том, что нет никакой необходимости проводить N поисков по M:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, тоже 1, то ищем индекс K в этой последовательноси на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.

Здравствуйте, cppguard, Вы писали:

C>Здравствуйте, landerhigh, Вы писали:

L>>Нет, там можно (и нужно) получить именно O(N+log(M))
L>>Имхо это может быть сложно увидеть сразу, но при попытке реализовать алгоритм станет очевидно.

C>Я задачу понял так: даны N последовательностей, каждая состоит из M значений. В каждый последовательности сперва идут нули, потом в какой-то момент начинают идти единицы. Нужно определить номер последовательности, в которой индекс первой единицы — наименьший. Если всё верно, то я бы очень хотел посмотреть на алгоритм O(N+log(M)) для этой задачи.

Дело в том, что нет никакой необходимости проводить N поисков по M:
В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательноси на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.