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

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

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