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.

def linear_search(matrix, target):
    for row in matrix:
        for element in row:
            if element == target:
                return True  # Element found
    return False  # Element not found

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
target = 7
if linear_search(matrix, target):
    print(f"Element {target} found in the matrix.")
else:
    print(f"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 bisect

def binary_search(matrix, target):
    for row in matrix:
        # Use binary search to find the target in the row
        if bisect.bisect_left(row, target) < len(row) and row[bisect.bisect_left(row, target)] == target:
            return True  # Element found
    return False  # Element not found

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
target = 10
if binary_search(matrix, target):
    print(f"Element {target} found in the matrix.")
else:
    print(f"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.

def search_in_sorted_matrix(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])
    i, j = 0, cols - 1  # Start from the top-right corner

    while i < rows and j >= 0:
        if matrix[i][j] == target:
            return True  # Element found
        elif matrix[i][j] > target:
            j -= 1  # Move left
        else:
            i += 1  # Move down
    return False  # Element not found

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
target = 5
if search_in_sorted_matrix(matrix, target):
    print(f"Element {target} found in the matrix.")
else:
    print(f"Element {target} not found in the matrix.")
            

Output:

Element 5 found in the matrix.