Median of two sorted lists

Median2.cs

// Return the median of a ∪ b ≠ ∅ if a and b are sorted
static double Median2(int[] a, int[] b)
{
    int m = a.Length;
    int n = b.Length;
    int h = (m + n + 1) / 2;                            // 'Half' - the number elements in the subset

    int Search(int lo, int hi) {
        if (lo == hi)
            return lo;                                  // No other choices left

        int i = (lo + hi) / 2;                          // The number of elements from a
        int j = h - i;                                  // The number of elements from b

        if (i < m && 0 < j && a[i] < b[j - 1])
            return Search(i + 1, hi);                   // a[i] should have been included
        if (j < n && 0 < i && b[j] < a[i - 1])
            return Search(lo, i - 1);                   // b[j] should have been included

        return i;                                       // We have the bottom h elements
    }

    int k = Search(h - Math.Min(h, n), Math.Min(h, m)); // The number of elements from a
    int l = h - k;                                      // The number of elements from b

    int top =                                           // The largest element of the subset
        k == 0 ? b[l - 1] :
        l == 0 ? a[k - 1] :
        Math.Max(a[k - 1], b[l - 1]);

    if ((m + n) % 2 == 1)                               // Return the middle element
        return top;

    int next =                                          // The smallest element of the rest
        k == m ? b[l] :
        l == n ? a[k] :
        Math.Min(a[k], b[l]);

    return (top + next) / 2.0;                          // Return the mean of both
}

Median2.hs

-- Return the median of a ∪ b ≠ ∅ if a and b are sorted
median2 :: Vector Int -> Vector Int -> Double
median2 a b
  | odd (m + n) = fromIntegral top
  | otherwise   = fromIntegral (top + next) / 2
  where
    m = length a
    n = length b
    h = (m + n + 1) `div` 2             -- 'Half' - the number elements in the subset

    k = search (h - min h n) (min h m)  -- The number of elements from a
    l = h - k                           -- The number of elements from b

    top                                 -- The largest element of the subset
      | k == 0 = b!(l - 1)
      | l == 0 = a!(k - 1)
      | otherwise = max (a!(k - 1)) (b!(l - 1))
    next                                -- The smallest element of the rest
      | k == m = b!l
      | l == n = a!k
      | otherwise = min (a!k) (b!l)

    search lo hi
      | lo == hi = lo                                         -- No other choices left
      | i < m && 0 < j && a!i < b!(j - 1) = search (i + 1) hi -- a!i should have been included
      | j < n && 0 < i && b!j < a!(i - 1) = search lo (i - 1) -- b!j should have been included
      | otherwise = i                                         -- We have the bottom h elements
      where
        i = (lo + hi) `div` 2           -- The number of elements from a
        j = h - i                       -- The number of elements from b