Алгоритм поиска элемента в отсортированной матрице размером MxN

Под отсортированной матрицей будем понимать такую матрицу, строки и столбцы которой отсортированы.

Чтобы найти нужный элемент, можно воспользоваться бинарным поиском по каждой строке. Алгоритм потребует O(M log(N)) времени, так как необходимо обработать М столбцов, на каждый из которых тратится O(log(N)) времени. Также можно обойтись и без сложного бинарного поиска. Мы разберем два метода.

Решение 1: обычный поиск

Прежде чем приступать к разработке алгоритма, давайте рассмотрим простой пример:

Допустим, мы ищем элемент 55. Как его найти?

Если мы посмотрим на первые элементы строки и столбца, то можем начать искать расположение искомого элемента. Очевидно, что 55 не может находиться в столбце, который начинается со значения больше 55, так как в начале столбца всегда находится минимальный элемент. Также мы знаем, что 55 не может находиться правее, так как значение первого элемента каждого столбца увеличивается слева направо. Поэтому, если мы обнаружили, что первый элемент столбца больше х, нужно двигаться влево.

Аналогичную проверку можно использовать и для строк. Если мы начали со строки, значение первого элемента которой больше х, нужно двигаться вверх.

Аналогичные рассуждения можно использовать и при анализе последних элементов столбцов или строк. Если последний элемент столбца или строки меньше х, то, чтобы найти х, нужно двигаться вниз (для строк) или направо (для столбцов). Это так, поскольку последний элемент всегда будет максимальным.

Давайте используем все эти наблюдения для построения решения:

• Если первый элемент столбца больше х, то х находится в колонке слева.
• Если последний элемент столбца меньше х, то х находится в колонке справа.
• Если первый элемент строки больше х, то х находится в строке, расположенной выше.
• Если последний элемент строки меньше х, то х находится в строке, расположенной ниже.

Давайте начнем со столбцов.

Мы должны начать с правого столбца и двигаться влево. Это означает, что первым элементом для сравнения будет [0][с-1], где с — количество столбцов. Сравнивая первый элемент столбца с х (в нашем случае 55), легко понять, что х может находиться в столбцах 0,1 или 2. Давайте начнем с [0][2].

Данный элемент может не являться последним элементом строки в полной матрице, но это конец строки в подматрице. А подматрица подчиняется тем же условиям. Элемент [0][2] имеет значение 40, то есть он меньше, чем наш элемент, а значит, мы знаем, что нам нужно двигаться вниз.

Теперь подматрица принимает следующий вид (серые ячейки отброшены):

Мы можем раз за разом использовать наши правила поиска. Обратите внимание, что мы используем правила 1 и 4.

Следующий код реализует этот алгоритм:

			public static boolean findElement(int[][] matrix, int elem) {
	int row = 0;
	int col = matrix[0].length - 1;
	while (row < matrix.length && col >= 0) {
		if (matrix[row][col] == elem) {
			return true;
		} else if (matrix[row][col] > elem) {
			col--;
		} else {
			row++;
		}
	}
	return false;
}
		

Другой подход к решению задачи — бинарный поиск. Мы получим более сложный код, но построен он будет на тех же правилах.

Решение 2: бинарный поиск

Давайте еще раз обратимся к нашему примеру:

Мы хотим повысить эффективность алгоритма. Давайте зададимся вопросом: где может находиться элемент?

Нам сказано, что все строки и столбцы отсортированы. Это означает, что элемент [i][j] больше, чем элементы в строке i, находящиеся между столбцами 0 и j и элементы в строке j между строками 0 и i-1.
Другими словами:

a[i][0] <= a[i][1] <= … <= a[i][j-i] <= a[i][j]a[0][j] <= a[1][j] <= … <= a[i-1][j] <= a[i][j]

Посмотрите на матрицу: элемент, который находится в темно-серой ячейке, больше, чем другие выделенные элементы.

Элементы в белых ячейках упорядочены. Каждый из них больше как левого элемента, так и элемента, находящегося выше. Таким образом, выделенный элемент больше всех элементов, находящихся в квадрате.

Можно сформулировать правило: нижний правый угол любого прямоугольника, выделенного в матрице, будет содержать самый большой элемент.

Аналогично, верхний левый угол всегда будет наименьшим. Цвета в приведенной ниже схеме отражают информацию об упорядочивании элементов (светло-серый < белый < темно-серый):

Давайте вернемся к исходной задаче. Допустим, что нам нужно найти элемент 85. Если мы посмотрим на диагональ, то увидим элементы 35 и 95. Какую информацию о местонахождении элемента 85 можно из этого извлечь?

85 не может находиться в темно-серой области, так как элемент 95 расположен в верхнем левом углу и является наименьшим элементом в этом квадрате.

85 не может принадлежать светло-серой области, так как элемент 35 находится в нижнем правом углу.

85 должен быть в одной из двух белых областей.

Таким образом, мы делим нашу сетку на четыре квадранта и выполняем поиск в нижнем левом и верхнем правом квадрантах. Их также можно разбить на квадранты и продолжить поиск.

Обратите внимание, что диагональ отсортирована, а значит, мы можем эффективно использовать бинарный поиск.

Приведенный ниже код реализует этот алгоритм:

			public Coordinate findElement(int[][] matrix, Coordinate origin, Coordinate dest, int x) {
	if (!origin.inbounds(matrix) || !dest.inbounds(matrix)) {
		return null;
	}
	if (matrix[origin.row][origin.column] == x) {
		return origin;
	} else if (!origin.isBefore(dest)) {
		return null;
	}

	/* Установим start на начало диагонали, a end - на конец
	* диагонали. Так как сетка, возможно, не является квадратной, конец
	* диагонали может не равняться dest. */
	Coordinate start = (Coordinate) origin.clone();
	int diagDist = Math.min(dest.row - origin.row, dest.column - origin.column);
	Coordinate end = new Coordinate(start.row + diagDist, start.column + diagDist);
	Coordinate p = new Coordinated(0, 0);

	/* Производим бинарный поиск no диагонали, ищем первый
	* элемент больше х */
	while (start.isBefore(end)) {
		р.setToAverage(start, end);
		if (x > matrix[p.row][p.column]) {
			start.row = p.row + 1;
			start.column = p.column + 1;
		} else {
			end.row = p.row - 1;
			end.column = p.column - 1;
		}
	}

	/* Разделяем сетку на квадранты. Ищем в нижнем левом и верхнем
	 * правом квадранте */
	return partitionAndSearch(matrix, origin, dest, start, x);
}

public Coordinate partitionAndSearch(int[][] matrix,
Coordinate origin. Coordinate dest, Coordinate pivot, int elem) {
	Coordinate lowerLeftOrigin = new Coordinate(pivot.row, origin.column);
	Coordinate lowerLeftDest = new Coordinate(dest.row, pivot.column - 1);
	Coordinate upperRightOrigin = new Coordinate(origin.row, pivot.column);
	Coordinate upperRightDest = new Coordinate(pivot.row - 1, dest.column);
	
	Coordinate lowerLeft = findElement(matrix, lowerLeftOrigin, lowerLeftDest, elem);
	if (lowerLeft == null) {
		return findElement(matrix, upperRightOrigin, upperRightDest, elem);
	}
	return lowerLeft;
}

public static Coordinate findElement(int[][] matrix, int x) {
	Coordinate origin = new Coordinate(0, 0);
	Coordinate dest = new Coordinate(matrix.length - 1, matrix[0].length - 1);
	return findElement(matrix, origin, dest, x);
}
public class Coordinate implements Cloneable {
	public int row;
	public int column;
	public Coordinate(int r, int c) {
		row = r;
		column = c;
	}

	public boolean inbounds(int[][] matrix) {
		return row >= 0 && column >= 0 &&
		row < matrix.length && column < matrix[0].length;
	}

	public boolean isBefore(Coordinate p) {
		return row <= p.row && column <= p.column;
	}

	public Object clone() {
		return new Coordinate(row, column);
	}

	public void setToAverage(Coordinate min, Coordinate max) {
		row = (min.row + max.row) / 2;
		column = (min.column + max.column) / 2;
	}
}
		

Этот код довольно трудно написать правильно с первого раза.

Запомните, что вы облегчите себе жизнь, выделяя код в методы. При написании программ, концентрируйтесь на ключевых местах. А собрать все воедино вы всегда сможете.