Search In A Row Wise And Column Wise Sorted Matrix

Searching for a specific element within a matrix can be a complex task, especially when dealing with large datasets. In this article, you will learn how to efficiently search for a target value in a matrix where elements are sorted both row-wise and column-wise, exploring various approaches to solve this common problem.

Problem Statement

A row-wise and column-wise sorted matrix is a 2D array where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. The problem is to find the position (row and column index) of a given target element within such a matrix. If the element is not found, an appropriate indication should be provided. This structure implies a global sortedness that can be exploited for faster searches than a simple linear scan.

Example

Consider the following 4x4 matrix, which is sorted both row-wise and column-wise:

10  20  30  40
15  25  35  45
27  29  37  48
32  33  39  50

If we are searching for the target 37, its position is (2, 2) (0-indexed). If we search for 31, it is not present in the matrix.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of the following concepts is helpful:

• Arrays and Matrices: How 2D arrays are structured and accessed using row and column indices.
• Loops: Iterating through elements using for or while loops.
• Binary Search: An efficient algorithm for finding an element in a sorted list.
• Time Complexity Analysis: Basic understanding of Big O notation (e.g., O(N), O(log N), O(N^2)).

Use Cases or Case Studies

Searching in sorted matrices has several practical applications across various domains:

• Database Indexing: Imagine a database table where data is naturally ordered by multiple keys (e.g., first by city, then by zip_code). A 2D sorted structure can represent efficiently queryable data.
• Image Processing: In some specialized image processing tasks, pixel values or feature descriptors might form a naturally sorted grid, requiring efficient searching for specific patterns or thresholds.
• Game Development: Pathfinding algorithms on grid-based maps where "cost" values are monotonically increasing or decreasing, or searching for nearby objects with specific attributes.
• Data Analysis and Visualization: When working with heatmaps or other grid-based data visualizations where values exhibit sorted properties, quickly locating specific value ranges or outliers.
• Geographic Information Systems (GIS): Searching for specific locations or features on a grid map where coordinates or property values are sorted.

Solution Approaches

We will explore three distinct approaches to solve this problem, ranging from naive to highly optimized.

Approach 1: Brute Force (Naive Approach)

This is the simplest approach, involving iterating through every element of the matrix and comparing it with the target.

• Summary: Traverse the entire matrix row by row, column by column, checking each element.
• Time Complexity: O(rows * columns)

// Brute Force Search in Sorted Matrix
#include <stdio.h>

void searchMatrixBruteForce(int matrix[4][4], int rows, int cols, int target) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == target) {
                printf("Target %d found at (%d, %d)\\n", target, i, j);
                return;
            }
        }
    }
    printf("Target %d not found in the matrix\\n", target);
}

int main() {
    int matrix[4][4] = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };
    int rows = 4;
    int cols = 4;
    int target1 = 37;
    int target2 = 31;

    // Step 1: Search for target1
    searchMatrixBruteForce(matrix, rows, cols, target1);

    // Step 2: Search for target2
    searchMatrixBruteForce(matrix, rows, cols, target2);

    return 0;
}

Run

• Sample Output:

  Target 37 found at (2, 2)
  Target 31 not found in the matrix

• Stepwise Explanation:

1. Initialize two nested loops: an outer loop for rows (i) from 0 to rows-1 and an inner loop for columns (j) from 0 to cols-1.
2. In each iteration, compare matrix[i][j] with the target.
3. If a match is found, print the coordinates and return.
4. If the loops complete without finding the target, print a "not found" message.

Approach 2: Binary Search on Each Row

Since each row is sorted, we can apply binary search to each row individually to find the target.

• Summary: Iterate through each row and perform a binary search within that row for the target element.
• Time Complexity: O(rows * log(columns))

// Binary Search on Each Row in Sorted Matrix
#include <stdio.h>

// Standard binary search function
int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid; // Element found
        }
        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // Element not found
}

void searchMatrixBinaryPerRow(int matrix[4][4], int rows, int cols, int target) {
    for (int i = 0; i < rows; i++) {
        int col_idx = binarySearch(matrix[i], 0, cols - 1, target);
        if (col_idx != -1) {
            printf("Target %d found at (%d, %d)\\n", target, i, col_idx);
            return;
        }
    }
    printf("Target %d not found in the matrix\\n", target);
}

int main() {
    int matrix[4][4] = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };
    int rows = 4;
    int cols = 4;
    int target1 = 29;
    int target2 = 100;

    // Step 1: Search for target1
    searchMatrixBinaryPerRow(matrix, rows, cols, target1);

    // Step 2: Search for target2
    searchMatrixBinaryPerRow(matrix, rows, cols, target2);

    return 0;
}

Run

• Sample Output:

  Target 29 found at (2, 1)
  Target 100 not found in the matrix

• Stepwise Explanation:

1. Define a helper function binarySearch that takes a sorted array, its bounds, and a target, returning the index if found, or -1 otherwise.
2. Iterate through each row of the matrix.
3. For each row, call binarySearch to find the target within that row.
4. If binarySearch returns a valid column index, the target is found. Print its coordinates and exit.
5. If all rows are checked and the target isn't found, print a "not found" message.

Approach 3: Optimized Staircase Search (Start from Top-Right or Bottom-Left)

This is the most efficient approach, exploiting the combined row-wise and column-wise sorted property. We can start from the top-right corner (or bottom-left) and eliminate rows or columns in each step.

• Summary: Start at the top-right corner. If the current element is equal to the target, return its position. If the current element is greater than the target, move left (discard current column). If the current element is less than the target, move down (discard current row).
• Time Complexity: O(rows + columns)

// Optimized Staircase Search in Sorted Matrix
#include <stdio.h>

void searchMatrixOptimized(int matrix[4][4], int rows, int cols, int target) {
    int row = 0;
    int col = cols - 1; // Start from top-right corner

    while (row < rows && col >= 0) {
        if (matrix[row][col] == target) {
            printf("Target %d found at (%d, %d)\\n", target, row, col);
            return;
        } else if (matrix[row][col] > target) {
            col--; // Target must be in the current row but to the left
        } else { // matrix[row][col] < target
            row++; // Target must be in the current column but below
        }
    }
    printf("Target %d not found in the matrix\\n", target);
}

int main() {
    int matrix[4][4] = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };
    int rows = 4;
    int cols = 4;
    int target1 = 39;
    int target2 = 12;

    // Step 1: Search for target1
    searchMatrixOptimized(matrix, rows, cols, target1);

    // Step 2: Search for target2
    searchMatrixOptimized(matrix, rows, cols, target2);

    return 0;
}

Run

• Sample Output:

  Target 39 found at (3, 2)
  Target 12 not found in the matrix

• Stepwise Explanation:

1. Initialize row = 0 (first row) and col = cols - 1 (last column), positioning the pointer at the top-right element.
2. Enter a while loop that continues as long as row is within bounds (< rows) and col is within bounds (>= 0).
3. Compare:
   • If matrix[row][col] equals the target, the element is found. Print its coordinates and exit.

1. If the loop finishes without finding the target, it means the target is not present in the matrix.

Conclusion

Searching in a row-wise and column-wise sorted matrix presents an interesting optimization challenge. While a brute-force approach is straightforward, it is highly inefficient for larger matrices. Performing binary search on each row improves efficiency significantly by leveraging the row-wise sorting. However, the most optimal solution is the "Staircase Search" which starts from a corner (e.g., top-right) and intelligently eliminates a row or a column in each step, achieving a linear time complexity proportional to the sum of rows and columns. This approach is highly recommended for its efficiency and elegance.

Summary

• Problem: Find a target element in a matrix sorted both row-wise and column-wise.
• Brute Force: Checks every element; O(rows * columns) time complexity.
• Binary Search per Row: Applies binary search to each row; O(rows * log(columns)) time complexity.
• Optimized Staircase Search: Starts from top-right (or bottom-left) and moves towards the target by eliminating rows or columns; O(rows + columns) time complexity.
• The optimized staircase search is the most efficient method due to its linear time complexity.