Staircase Search On Sorted 2D Matrices in C++

Filed Under: C++
Staircase Search On Sorted 2D Matrices

In this article, we will go through the underlying algorithm behind staircase search on sorted 2D matrices. 2D matrices are very common in real-life applications, most of the images that we click are nothing but two-dimensional matrices of colors.

We can perform several operations on matrices. And the operation that we will discuss in this article is searching for a particular element. The brute force search is always available to us but, it fails for large-sized matrices and is very inefficient. This is the reason why we use the staircase search. Let’s see what does staircase search means?

What Is A Staircase Search

Given that we have a row and column-wise sorted 2D matrix of order M x N, our task is to search for an element key in the matrix.

Since we have a sorted matrix, instead of searching at every position, we will now limit our search with every next move.

Concept Behind Staircase Search

To implement a 2D staircase search we will follow the following steps to code the algorithm.

  • Start from the position –> (0, 0)
  • At each step we make some arithmetic decisions
  • Initialize two variables i = 0 and j = N – 1
  • Now check if key == matrix[i][j]
    • If yes, then return the position i.e. (i, j)
    • Else we will do the following computation
      • Check if key < matrix[i][j]
        • If yes, then limit the search area to the previous column, i.e. j – 1
      • Otherwise, key > matrix[i][j]
        • In this case, we can only search in the same column, i.e. from row i to row (M – 1)
Example 6
Example

Algorithm for Staircase Search On Sorted 2D Matrices in C++

pair <int, int> staircase_search(vector <vector <int>> v, int key)
{
        int i = 0;
        int j = v[0].size() - 1;

        while(!(i == v.size() || j == -1))
        {
                // compare the current element
                if(v[i][j] == key)
                        return make_pair(i, j);

                // otherwise
                else if(v[i][j] < key)
                        i = i + 1;

                else
                        j = j - 1;
        }

        return make_pair(-1, -1);
}
Algorithm 6
Staircase Search On Sorted 2D Matrices Algorithm

Staircase Search On Sorted 2D Matrices Program Using C++

#include <iostream>
#include <vector>

using namespace std;

pair <int, int> staircase_search(vector <vector <int>> v, int key)
{
	int i = 0;
	int j = v[0].size() - 1;

	while(!(i == v.size() || j == -1))
	{
		// compare the current element
		if(v[i][j] == key)
			return make_pair(i, j);

		// otherwise
		else if(v[i][j] < key)
			i = i + 1;

		else
			j = j - 1;
	}

	return make_pair(-1, -1);
}

int main()
{
	cout << "Enter the dimensions of the vector" << endl;
	int m, n;
	cin >> m >> n;

	cout << "Enter the elements of the vector" << endl;

	vector <vector <int>> v(m, vector <int> (n, 0));
	for(int i = 0; i < m; i++)
		for(int j = 0; j < n; j++)
			cin >> v[i][j];

	cout << "Enter the key" << endl;
	int key;
	cin >> key;

	pair <int, int> location = staircase_search(v, key);

	if(location.first == -1 || location.second == -1)
		cout << "Key is not present in the matrix" << endl;
	else
		cout << "Key found at the location: [" << location.first << ", " << location.second << "]" << endl;

	return 0;
}

Output

Staircase Search Output
Staircase Search On Sorted 2D Matrices Output

Time And Space Complexity Analysis

Staircase search uses no extra space. The overall space complexity boils down to O(1).

The time complexity of the brute force approach is O(M x N). That is quadratic time complexity, this time complexity fails to give the results for M and N greater than 103. This is the reason why we avoid this method.

On the other hand, the staircase search is way more efficient than the brute force approach. Because even in the worst case we would need to travel from position (0, N – 1) to the position (M – 1, 0). This implies that the worst-case complexity would be O(M + N)

Conclusion

Let’s conclude this article by recalling what did we learn today. First, we looked at the staircase approach, then we wrote the algorithm. In the end, we wrote a C++ program to test the algorithm. That’s all for today, thanks for reading.

Further Readings

To learn more about vectors and sorting, you can refer to the following articles

https://www.journaldev.com/56329/merge-sort-in-cpp

https://www.journaldev.com/56360/vector-class-in-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content