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.

public class MatrixSearch {
    public static boolean linearSearch(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int element : row) {
                if (element == target) {
                    return true; // Element found
                }
            }
        }
        return false; // Element not found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };
        int target = 7;
        if (linearSearch(matrix, target)) {
            System.out.println("Element " + target + " found in the matrix.");
        } else {
            System.out.println("Element " + target + " not found in the matrix.");
        }
    }
}
            

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.

import java.util.Arrays;

public class MatrixSearch {
    public static boolean binarySearch(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (Arrays.binarySearch(row, target) >= 0) {
                return true; // Element found
            }
        }
        return false; // Element not found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };
        int target = 10;
        if (binarySearch(matrix, target)) {
            System.out.println("Element " + target + " found in the matrix.");
        } else {
            System.out.println("Element " + target + " not found in the matrix.");
        }
    }
}
            

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.

public class MatrixSearch {
    public static boolean searchInSortedMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        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
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };
        int target = 5;
        if (searchInSortedMatrix(matrix, target)) {
            System.out.println("Element " + target + " found in the matrix.");
        } else {
            System.out.println("Element " + target + " not found in the matrix.");
        }
    }
}
            

Output:

Element 5 found in the matrix.