F# on Algorithms - Find median from two sorted array

Find median from two sorted arrays is another typical questions. Feel dizzy when seeing indexes in the algorithm? I am with you.. :)

In this sample, I want to show how to use Active Pattern to decompose the data. From the code itself, you can easily find the hint of the data. If you see (l, value, r) which is from a sorted list. Most likely, the l, value, and r are in order. Also the Array slicing is a nice syntax feature as well.


let getMedian (list:float array) =
    let len = list.Length
    if len % 2 = 0 then
        (list.[len/2-1] + list.[len/2]) / 2.
    else
        list.[len/2]

let (|Median|) (list:float array) =
    let median = getMedian list
    let len = list.Length
    if len % 2 = 0 then
        (list.[0..len/2-1], median, list.[len/2..])
    else
        (list.[0..len/2], median, list.[len/2..])

let rec getMedianFromTwo (list0:float array) (list1:float array) =
    match list0, list1 with
    | [||], [||] -> 0.
    | [|a|], [|b|] -> (a+b) / 2.
    | [|a0; a1|], [|b0; b1|] -> ((max a0 b0) + (min a1 b1)) / 2.
    | Median(l0, m0, r0), Median(l1, m1, r1) ->
        if m0 = m1 then
            m0
        elif m0 < m1 then
            getMedianFromTwo r0 l1
        else //m0 > m1
            getMedianFromTwo l0 r1

let list0 = [|1.;4.;7.;8.;9.;10.|]
let list1 = [|2.;4.;6.;7.;9.;15.|]

let c = getMedianFromTwo list0 list1

Tweet to fsharp