Find The Minimum Difference
October 15, 2013
This is rather straight forward, though I admit it took a few tries to get all the less thans and minus signs in the right place:
(define (f xs ys)
(let ((d (- (car xs) (car ys))))
(let loop ((xs xs) (ys ys) (diff (abs d)))
(cond ((or (null? xs) (null? ys)) diff)
((< (car xs) (car ys))
(let ((d (- (car ys) (car xs))))
(loop (cdr xs) ys (min d diff))))
(else (let ((d (- (car xs) (car ys))))
(loop xs (cdr ys) (min d diff))))))))
> (f '(19 22 24) '(37 38 49 88))
The difference of 13 appears between 24 of the first array and 37 of the second array.
Assuming that the longer of the two arrays has length n, the algorithm given above has time complexity O(n). If the arrays weren’t sorted, you could sort them and then scan, giving a O(n log n) algorithm, or you could compare the items one-by-one for an O(n2) algorithm.
You can run the program at http://programmingpraxis.codepad.org/4bWj9XMf.
Pages: 1 2