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

S>>Ведь тогда на шагах со второго по последний нам придется делать одинаковые поиски со сложностью O(log(M-1)). Разве нет?

L>В этом случае, в шагах, начиная со второгшо по последний, поиски проводить вообще не требуется.

Э...

если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]

На втором шаге вы обнаруживаете 1 по индексу K (при этом K==(M-1)). Вы знаете, что по индексу K единица, но не знаете, первая ли это единица в строке или нет. Чтобы это узнать, вам нужно сделать поиск единиц слева от K (т.е. в диапазоне [0, (K-1)]).

И, поскольку K у вас не меняется, на каждой следующей итерации вы должны будете проделывать тоже самое.