Finding the element in the M X N matrix sorted in ascending order

Problem

Given an M $\times$ N matrix in which each row and each column are sorted in ascending order, write a method to find an element.

Binary search approach, $O( \log {N \times N})$

This is one of the binary search variations. If we split the matrix into M rows and stitch them together, we will have the one-dimensional array with N $\times$ M elements sorted in ascending order. (See Figure 1)

Now, we can perform the binary search within the range between 0 and $N \times M -1$. Once we get the position of the element in the middle, h We need to convert it into the coordinates within the matrix following formula:

  Column position  = h / N

  Row position = h % N

 Once the coordinates are calculated, we can compare them with the target value as we do in the binary search. The rest of the algorithm will be the same as the typical binary search.

Overall running time will be $$O(\log {N \times M})$$

Here is the complete code in C++.

	#include<iostream>
	using namespace std;
	bool search(int** matrix, int N, int s, int e, int target)
	{
	if (s > e)
	return false;
	int h = s + (e-s)/2;
	int m = h/N;
	int n = h%N;
	bool found;
	if (matrix[m][n] == target)
	found = true;
	else if (matrix[m][n] < target)
	found = search(matrix, N, h+1, e, target);
	else
	found = search(matrix, N, s, h-1, target);
	return found;
	}
	int main()
	{
	int N = 6, M = 7;
	int target = 13;
	int ** input = new int*[M];
	for(int i = 0; i < M; i++)
	input[i] = new int[N];
	for(int i = 0; i < M; i++)
	for(int j = 0; j <N; j++)
	input[i][j] = i*N+j;
	cout<<"find "<<target<<" = "<<search(input, N, 0, M*N-1, target) << endl;
	return 1;
	}

view raw binary_search_in_matrix.cpp hosted with ❤ by GitHub

Here is another solution in python

	class Matrix:
	def __init__(self, matrix, row, column):
	self.matrix = matrix
	self.row = row
	self.column = column
	def binary_search(self, num, start, end):
	if (start > end):
	return None
	half = start + (end - start)/2
	value = self.matrix[half/self.column][half % self.column]
	if (num == value):
	return value
	elif (num > value):
	start = half + 1
	else:
	end = half - 1
	return self.binary_search(num, start, end)
	def find_element(self, num):
	start = 0
	end = self.row * self.column -1
	return self.binary_search(num, start, end)
	#example code
	row = 4
	column = 5
	input = [ [i+1+column*j for i in range(column)] for j in range(row) ]
	matrix = Matrix(input, row, column)
	print ('find 2 in matrix :', matrix.find_element(2))
	print ('find 5 in matrix :', matrix.find_element(5))
	print ('find 15 in matrix :', matrix.find_element(15))
	print ('find 20 in matrix :', matrix.find_element(20))
	print ('find 16 in matrix :', matrix.find_element(16))
	print ('find 21 in matrix :', matrix.find_element(21))

view raw binary_search_in_matrix.py hosted with ❤ by GitHub

Practice statistics

19:30: to write up the solution

UPDATE(2022-06-13): Solved the problem again. The initial algorithm had the flaw in converting the linear position into the matrix position. Mistakenly used the number of rows when calculating the row position. Should've used the row length to get the correct value.

	# code
	class MatrixBinarySearch:
	def __init__(self, width, height, matrix):
	self.width = width
	self.height = height
	self.matrix = matrix
	def get_value_in_matrix(self, pos):
	x = pos % self.width
	y = pos // self.width
	print("x = {}, y = {}".format(x, y))
	return self.matrix[y][x]
	def binary_search(self, target, min, max):
	if min > max:
	return False
	half = (min + max)//2
	value = self.get_value_in_matrix(half)
	if value == target:
	return True
	# search the right half
	if target > value:
	return self.binary_search(target, half + 1, max)
	# search the left half
	return self.binary_search(target, min, half - 1)
	def search(self, target):
	min = 0
	max = self.width * self.height - 1
	return self.binary_search(target, min, max)
	# test
	# 3 X 4 matrix
	input = [
	[1, 2, 3, 4],
	[5, 6, 7, 8],
	[9, 10, 11, 12]
	]
	finder = MatrixBinarySearch(width=4, height=3, matrix=input)
	target = 6
	is_exist = finder.search(target)
	print("does {} in the matrix. {}".format(target, is_exist))
	target = 1
	is_exist = finder.search(target)
	print("does {} in the matrix. {}".format(target, is_exist))
	target = 12
	is_exist = finder.search(target)
	print("does {} in the matrix. {}".format(target, is_exist))
	target = 13
	is_exist = finder.search(target)
	print("does {} in the matrix. {}".format(target, is_exist))

view raw binary_search_in_matrix.py hosted with ❤ by GitHub