December 6, 2016
The obvious solution is to merge the two arrays, then take the median. Since the two arrays are already sorted, the merge takes O(n), and the median is then O(1):
(define (med1 lt? xs ys) (let* ((zs (merge lt? xs ys)) (n (length zs))) (list-ref zs (quotient n 2)))) > (med1 < '(1 3 5 7 9) '(2 4 6 8)) 5
We uses lists instead of arrays, so the median is O(n) instead of O(1). If you don’t like that, here we perform the merge ourselves, stopping when we find the median:
(define (med2 lt? xs ys) (let ((n (quotient (+ (length xs) (length ys) 1) 2))) (let loop ((n (- n 1)) (xs xs) (ys ys)) (cond ((zero? n) (car xs)) ((lt? (car xs) (car ys)) (loop (- n 1) (cdr xs) ys)) ((lt? (car ys) (car xs)) (loop (- n 1) xs (cdr ys))) (else (loop (- n 1) (cdr xs) ys)))))) > (med2 < '(1 3 5 7 9) '(2 4 6 8)) 5
The solutions at Career Cup suggest that an O(log n) solution is possible, but I’m not convinced. It seems to me that all of the binary search solutions can be defeated by the two arrays [1,1,1,1,1] and [3,3,3,3], for which the median of the combined array is 1.
You can run the program at http://ideone.com/rHWd8o.
Pages: 1 2