Дана матрица M×N целых чисел со свойствами:
- каждая строка отсортирована по неубыванию;
- первый элемент каждой строки не меньше последнего элемента предыдущей.
Иначе говоря, если выписать строки подряд, получится отсортированный массив.
Определите, есть ли в матрице число target.
// SearchMatrix сообщает, есть ли target в отсортированной матрице.
func SearchMatrix(matrix [][]int, target int) bool
Примеры
matrix = [[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]]
target = 3 → true
target = 13 → false
Ограничения
0 ≤ M, N, M·N ≤ 10⁶, матрица прямоугольная (пустая матрица или пустые
строки — ответ false).- Матрицу менять нельзя.
- Ожидается O(log(M·N)) на запрос. Функцию вызывают много раз, в том числе
на матрицах формы
1×10⁶ и 10⁶×1 — обход «лесенкой» за O(M+N) не уложится.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.