Example: Optimized Staircase Search in Sorted Matrix in C

// 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;
}