URL

Search in Rotated Sorted Array - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202308/search_in_rotated_sorted_array/main.fsx

let search (nums: int[]) (target: int) : int =
    let rec findPivot (nums: int[]) left right =
        if left > right then
            left
        else
            let mid = left + (right - left) / 2

            if nums.[mid] > nums.[nums.Length - 1] then
                findPivot nums (mid + 1) right
            else
                findPivot nums left (mid - 1)

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

            if nums.[mid] = target then
                mid
            elif nums.[mid] < target then
                binarySearch nums (mid + 1) right target
            else
                binarySearch nums left (mid - 1) target

    let pivot = findPivot nums 0 (nums.Length - 1)
    let ret = binarySearch nums 0 (pivot - 1) target

    if ret <> -1 then
        ret
    else
        binarySearch nums pivot (nums.Length - 1) target