Нет, разумеется, тоже методом половинного деления (ну или интерполяционным поиском). Просто делить придётся меньший диапазон, не миллиарды от l до zzzzzzzzzz, а миллионы от l до lzsdkfbv. Что даст нам экономию в ~8 сравнений уже на третьей итерации. Навскидку, должно получиться что-нибудь вроде O(log M log N), но, возможно, я ошибаюсь.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
(no subject)
Date: 2015-11-17 11:50 am (UTC)Навскидку, должно получиться что-нибудь вроде O(log M log N), но, возможно, я ошибаюсь.