Поиск элемента в матрице, отсортированной по строкам и столбцам, может оказаться сложной задачей. В этой статье мы рассмотрим несколько эффективных методов решения этой проблемы. Мы предоставим примеры кода для каждого метода, чтобы проиллюстрировать его реализацию. Давайте погрузимся!

Метод 1: линейный поиск
Самый простой подход — выполнять линейный поиск по каждой строке или столбцу, пока целевой элемент не будет найден. Этот метод имеет временную сложность O(m*n), где m — количество строк, а n — количество столбцов в матрице. Вот пример кода на Python:

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

Метод 2: двоичный поиск
Поскольку матрица отсортирована, мы можем применить двоичный поиск для повышения эффективности поиска. Мы можем выполнять двоичный поиск по каждой строке или столбцу индивидуально. Этот метод имеет временную сложность O(mlog(n)) или O(nlog(m)), в зависимости от того, выполняем ли мы поиск по строкам или по столбцам. Вот пример бинарного поиска в Python:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False
def matrix_search(matrix, target):
    for row in matrix:
        if binary_search(row, target):
            return True
    return False

Метод 3: разделяй и властвуй
Мы можем использовать подход «разделяй и властвуй» для эффективного поиска в матрице. Мы делим матрицу на четыре квадранта и рекурсивно ищем в соответствующем квадранте на основе целевого элемента и свойства сортировки матрицы. Этот метод имеет временную сложность O(n^(log2(4))) или O(n^2), где n — размерность матрицы. Вот пример кода на Python:

def search_quadrant(matrix, target, row_start, row_end, col_start, col_end):
    if row_start > row_end or col_start > col_end:
        return False
    mid_row = (row_start + row_end) // 2
    mid_col = (col_start + col_end) // 2
    mid_element = matrix[mid_row][mid_col]
    if mid_element == target:
        return True
    elif mid_element > target:
        return search_quadrant(matrix, target, row_start, mid_row - 1, col_start, col_end) or \
               search_quadrant(matrix, target, mid_row, row_end, col_start, mid_col - 1)
    else:
        return search_quadrant(matrix, target, mid_row + 1, row_end, col_start, col_end) or \
               search_quadrant(matrix, target, row_start, mid_row, mid_col + 1, col_end)
def matrix_search(matrix, target):
    return search_quadrant(matrix, target, 0, len(matrix) - 1, 0, len(matrix[0]) - 1)

Метод 4: оптимальный подход
Наиболее эффективный подход — начать с верхнего правого или нижнего левого угла матрицы и двигаться в определенном направлении на основе сравнения целевого элемента с текущим элементом. Этот метод исключает строки или столбцы при каждом сравнении, что приводит к временной сложности O(m + n). Вот пример кода на Python:

def matrix_search(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])
    row = 0
    col = cols - 1
    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1
    return False

В этой статье мы обсудили различные методы поиска элемента в матрице, отсортированной по строкам и столбцам. Мы рассмотрели линейный поиск, бинарный поиск, разделяй и властвуй, а также оптимальный подход. Каждый метод имеет свои преимущества и недостатки, но оптимальный подход обеспечивает наилучшую временную сложность. В зависимости от конкретных требований и ограничений вашей проблемы вы можете выбрать наиболее подходящий метод. Удачных поисков!