Постановка задачи — проверить, присутствует ли элемент в матрице размера n*m, в которой строки и столбцы отсортированы по возрастанию.
Образец ввода -
[ [1, 3, 12],
[2, 4 , 20],
[5, 10, 30]]
k=4
Вывод
истинный
Решение:
Первоначальная мысль состоит в том, чтобы применить бинарный поиск к каждой строке, и если в какой-либо из строк есть элемент, то вернуть true, иначе вернуть false.
Временная сложность решения составляет O (n log m), что лучше, чем решение грубой силы, когда вы перебираете все элементы, что приводит к O (n * m)
Это можно решить лучше, используя бинарный поиск.
Примечание. Строки и столбцы располагаются в отсортированном порядке, поэтому элемент, находящийся в левой ячейке текущего элемента, будет меньше текущего значения, а элемент, находящийся под текущим элементом, будет больше текущего значения.
давайте рассмотрим элемент 4 в приведенном выше образце ввода, элемент, присутствующий слева от 4, будет меньше (2‹4), а элемент, присутствующий под элементом 4, будет больше, чем 4 (4‹10)
поэтому, если мы начнем с верхнего правого углового элемента матрицы, мы можем сравнить целевой элемент с текущим элементом и соответственно двигаться в соответствии с сравнением.
скажем, в приведенном выше примере-
Элемент в верхнем правом углу равен 12, а целевой элемент равен 4.
если текущий элемент меньше целевого элемента, то переместитесь в ячейку под ним, потому что мы знаем, что нижний элемент будет больше, чем текущий элемент, иначе переместитесь в левую ячейку текущего элемента, поэтому в этом случае мы переместим левую ячейку элемент 12, который является элементом 3, и если мы снова сравним с целевым элементом 4, то мы переместимся ниже, поскольку текущий элемент меньше целевого, поэтому мы нашли целевой элемент 4
поскольку размер матрицы равен n * m, поэтому из правого верхнего угла мы можем переместить n ячеек ниже и m ячеек влево от верхнего левого угла.
Следовательно, временная сложность O (n + m)
КОД —
общедоступный логический brinarySearch (int grid [][], int k) {
int n = grid.length;
int m = сетка [0]. длина;
if(k ‹ сетка[0][0] || k› сетка[n-1][m-1])
вернуть ложь;
интервал i=0, j=m-1; \\ положение в правом верхнем углу
в то время как (j≥0 && i‹n){
если (сетка [i] [j] == k)
вернуть истину;
иначе если (сетка[i][j] › k)
j-- ;
еще
i++;
}
вернуть ложь;
}
