Код Senior Бинарный поиск обновлено
Поиск в отсортированной матрице
Условие
Матрица, где каждая строка отсортирована и первый элемент строки больше последнего элемента предыдущей. Есть ли target?
Примеры
searchMatrix([[1, 3, 5], [7, 9, 11]], 9) // true
searchMatrix([[1, 3]], 2) // false
searchMatrix([]) // false
Как подойти
Сведение двумерной задачи к одномерной: mid → [mid / cols][mid % cols]. O(log(m·n)) вместо поиска строки и потом в строке. Если условие слабее (строки и столбцы отсортированы независимо) - работает лестничный поиск из угла за O(m+n).
Подсказки: 2
- Такая матрица - это один отсортированный массив, свёрнутый в строки.
- Индекс i превращается в координаты делением и остатком.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.