Matrix-Search-D&C

package main

import (
"fmt"
)

func main() {
    // Example usage
    X := [][]int{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9},
    }

    k := 5
    topLeftI := 0
    topLeftJ := 0
    bottomRightI := len(X) - 1
    bottomRightJ := len(X[0]) - 1

    result := find(X, k, topLeftI, topLeftJ, bottomRightI, bottomRightJ)

    if result[0] == -1 && result[1] == -1 {
        fmt.Println("Element not found.")
    } else {
        fmt.Printf("Element found at position (%d, %d).\n", result[0], result[1])
    }
    }

func find(X [][]int, k, topLeftI, topLeftJ, bottomRightI, bottomRightJ int) [2]int {
    mI := (topLeftI + bottomRightI) / 2
    mJ := (topLeftJ + bottomRightJ) / 2

    if X[mI][mJ] == k {
    return [2]int{mI, mJ}
    }

    if topLeftI == bottomRightI && topLeftJ == bottomRightJ {
        return [2]int{-1, -1} // not found
    }

    if topLeftI > bottomRightI || topLeftJ > bottomRightJ {
        return [2]int{-1, -1} // not found
    }

    if X[mI][mJ] > k {
        pos := find(X, k, topLeftI, topLeftJ, mI-1, mJ-1)
        if pos != [2]int{-1, -1} {
            return pos
        }

        pos = find(X, k, mI, topLeftJ, bottomRightI, mJ-1)
        if pos != [2]int{-1, -1} {
            return pos
        }

        pos = find(X, k, topLeftI, mJ, mI-1, bottomRightJ)
        if pos != [2]int{-1, -1} {
            return pos
        }
        } else {
        pos := find(X, k, mI+1, mJ+1, bottomRightI, bottomRightJ)
        if pos != [2]int{-1, -1} {
            return pos
        }

        pos = find(X, k, mI+1, topLeftJ, bottomRightI, mJ)
        if pos != [2]int{-1, -1} {
            return pos
        }

        pos = find(X, k, topLeftI, mJ+1, mI, bottomRightJ)
        if pos != [2]int{-1, -1} {
            return pos
        }
    }

    return [2]int{-1, -1} // not found
}