Search an Element in a Matrix

Understanding the Problem

The goal is to search for an element in a matrix.

Method 1: Linear Search

This method uses a simple linear search to find the element in the matrix.

#include <iostream>
using namespace std;

bool linearSearch(int matrix[][100], 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) {
                return true; // Element found
            }
        }
    }
    return false; // Element not found
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    int target = 7;
    int rows = 4, cols = 4;
    if (linearSearch(matrix, rows, cols, target)) {
        cout << "Element " << target << " found in the matrix." << endl;
    } else {
        cout << "Element " << target << " not found in the matrix." << endl;
    }
    return 0;
}

Output:

Element 7 found in the matrix.

Method 2: Binary Search (Row-wise Sorted)

This method assumes that each row of the matrix is sorted and uses binary search.

#include <iostream>
#include <algorithm>
using namespace std;

bool binarySearch(int matrix[][100], int rows, int cols, int target) {
    for (int i = 0; i < rows; i++) {
        if (binary_search(matrix[i], matrix[i] + cols, target)) {
            return true; // Element found
        }
    }
    return false; // Element not found
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    int target = 10;
    int rows = 4, cols = 4;
    if (binarySearch(matrix, rows, cols, target)) {
        cout << "Element " << target << " found in the matrix." << endl;
    } else {
        cout << "Element " << target << " not found in the matrix." << endl;
    }
    return 0;
}

Output:

Element 10 found in the matrix.

Method 3: Search in a Sorted Matrix

This method assumes the matrix is sorted in a way that each row and column is sorted. It uses an efficient approach starting from the top-right corner.

#include <iostream>
using namespace std;

bool searchInSortedMatrix(int matrix[][100], int rows, int cols, int target) {
    int i = 0, j = cols - 1; // Start from the top-right corner
    while (i < rows && j >= 0) {
        if (matrix[i][j] == target) {
            return true; // Element found
        } else if (matrix[i][j] > target) {
            j--; // Move left
        } else {
            i++; // Move down
        }
    }
    return false; // Element not found
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    int target = 11;
    int rows = 4, cols = 4;
    if (searchInSortedMatrix(matrix, rows, cols, target)) {
        cout << "Element " << target << " found in the matrix." << endl;
    } else {
        cout << "Element " << target << " not found in the matrix." << endl;
    }
    return 0;
}

Output:

Element 11 found in the matrix.

Explanation:

This method works efficiently (O(m+n) time complexity) for matrices where:

Each row is sorted in ascending order from left to right
Each column is sorted in ascending order from top to bottom

The algorithm starts at the top-right corner and eliminates either a row or column in each step:

If current element > target: move left (eliminate current column)
If current element < target: move down (eliminate current row)