Shohei Yoshida
Shohei Yoshida's Blog

Shohei Yoshida's Blog

LeetCode 240. Search a 2D Matrix II in F#

Shohei Yoshida's photo
Shohei Yoshida
·Jul 24, 2022·

1 min read

URL

leetcode.com/problems/search-a-2d-matrix-ii

Code

github.com/syohex/dotnet-study/blob/master/..

let searchMatrix (matrix: int [,]) (target: int) : bool =
    let binarySearch pos isRow target (matrix: int [,]) =
        let rec binarySearch' left right pos isRow target (matrix: int [,]) =
            if left > right then
                false
            else
                let index = (left + right) / 2

                let mid =
                    if isRow then
                        matrix.[pos, index]
                    else
                        matrix.[index, pos]

                if target = mid then
                    true
                elif target < mid then
                    binarySearch' left (index - 1) pos isRow target matrix
                else
                    binarySearch' (index + 1) right pos isRow target matrix

        let right =
            if isRow then
                (Array2D.length1 matrix) - 1
            else
                (Array2D.length2 matrix) - 1

        binarySearch' 0 right pos isRow target matrix


    let rec searchMatrix' i limit (matrix: int [,]) =
        if i >= limit then
            false
        else
            let rowFound = binarySearch i true target matrix
            let colFound = binarySearch i false target matrix

            if rowFound || colFound then
                true
            else
                searchMatrix' (i + 1) limit matrix

    let limit = System.Math.Min(Array2D.length1 matrix, Array2D.length2 matrix)
    searchMatrix' 0 limit matrix
 
Share this