Почему это работает
- Каждая строка отсортирована и начинается выше конца предыдущей, поэтому строки, прочитанные одна за другой, — это один отсортированный список из строки · столбцы чисел.
- Бинарный поиск идёт по индексам этого списка, не собирая его: индекс k — это строка floor(k / cols), столбец k mod cols. Здесь mid = 8 попадает на 23 — первое число строки 2.
- Один поиск по всем клеткам занимает около log(строки · столбцы) шагов, столько же, сколько найти сначала строку, а потом искать внутри неё.
Сложность
Время O(log(m · n)) для m строк и n столбцов: каждый шаг делит диапазон клеток пополам. Память O(1): матрица в список не копируется.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗