## Sunday, September 30, 2012

### 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