Shohei Yoshida
Shohei Yoshida's Blog

Shohei Yoshida's Blog

LeetCode 34. Find First and Last Position of Element in Sorted Array in F#

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

1 min read

URL

leetcode.com/problems/find-first-and-last-p..

Code

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

let searchRange (nums: int []) (target: int) : (int * int) =
    let rec checkUnder pos (nums: int []) target =
        if pos < 0 then 0
        elif nums.[pos] <> target then pos + 1
        else checkUnder (pos - 1) nums target

    let rec checkUpper pos (nums: int []) target =
        if pos >= nums.Length then
            nums.Length - 1
        elif nums.[pos] <> target then
            pos - 1
        else
            checkUpper (pos + 1) nums target

    let rec searchRange' left right (nums: int []) target =
        if left > right then
            -1, -1
        else
            let mid = (left + right) / 2

            if nums.[mid] = target then
                checkUnder (mid - 1) nums target, checkUpper (mid + 1) nums target
            elif nums.[mid] < target then
                searchRange' (mid + 1) right nums target
            else
                searchRange' left (mid - 1) nums target

    searchRange' 0 (nums.Length - 1) nums target
 
Share this