Matrix-Search-D&C

from typing import List

def find(X: List[List[int]], k: int, top_left_i: int, top_left_j: int, bottom_right_i: int, bottom_right_j: int):
    m_i = (top_left_i + bottom_right_i) // 2
    m_j = (top_left_j + bottom_right_j) // 2

    if X[m_i][m_j] == k:
        return (m_i, m_j)

    if top_left_i == bottom_right_i and top_left_j == bottom_right_j:
        return (-1, -1)  # not found

    if top_left_i > bottom_right_i or top_left_j > bottom_right_j:
        return (-1, -1)  # not found

    if X[m_i][m_j] > k:
        pos = find(X, k, top_left_i, top_left_j, m_i - 1, m_j - 1)
        if pos != (-1, -1):
            return pos

        pos = find(X, k, m_i, top_left_j, bottom_right_i, m_j - 1)
        if pos != (-1, -1):
            return pos

        pos = find(X, k, top_left_i, m_j, m_i - 1, bottom_right_j)
        if pos != (-1, -1):
            return pos

    else:
        pos = find(X, k, m_i + 1, m_j + 1, bottom_right_i, bottom_right_j)
        if pos != (-1, -1):
            return pos

        pos = find(X, k, m_i + 1, top_left_j, bottom_right_i, m_j)
        if pos != (-1, -1):
            return pos

        pos = find(X, k, top_left_i, m_j + 1, m_i, bottom_right_j)
        if pos != (-1, -1):
            return pos

    return (-1, -1)  # not found