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

C>Ага, и сложность вышеописанного алгоритма — O(N * log(M)) в худшем случае:

	Скрытый текст
	C> C>0 0 ... 0 0 1 C>0 0 ... 0 1 1 C>............. C>1 1 ... 1 1 1 C>

Позволю себе не согласиться:

0 0 ... 0 0 1
0 0 ... 0 1 1
.............
0 1 ... 1 1 1
1 1 ... 1 1 1

Мы никогда не повторяем поиск по M, т.к. на каждом шаге M уменьшается.

А дальше получаем, что имеем дело с O(log(1)) + O(log(2)) + .. + O(log(N-1)) + O(log(N)) = O(log(N))