MIT Scheme median procedure

Question

How would you go about defining a procedure to find the median of a list without using list-ref? For example, (median '(1 2 2)) would return 2 and (median '(1 2 3 4 5 6)) would return 3.5. You can assume that it is a list of sorted integers.

This is a homework question, so please don't post the actual code. All I'm looking for is some hints or some pseudo code to help push me in the right direction. As stated in the title I am using MIT Scheme. Thanks in advance.

Answer 1

Do you know how to use the tortoise-and-hare algorithm? If so, after your algorithm completes, your tortoise will be at the middle of the list.

If you're really stuck, I have a working implementation. Or, here's some pseudocode-like thing:

(define (median lst)
  (if (null? lst) #f                         ;; oops, empty list
      (let loop ((tortoise <???>)
                 (hare <???>))
        (cond ((eq? tortoise hare) #f)       ;; oops, circular list
              ((null? hare) <???>)           ;; median value here
              ((null? (cdr hare)) <???>)     ;; average of middle two elements
              (else (loop <???> <???>))))))  ;; keep going

Answer 2

In the case where the median is the average of the two middle elements in the list, using list-ref will be inefficient. The reason is that you would skip over the first half of the list twice to find the two middle elements.

One solution is to write a helper function (drop-list a-list n) that drops the first n elements of the list. E.g. (drop-list '(a b c d e) 2) is '(c d e). Using drop-list you can now do the following:

1. Find the length of the list
2. If the length is odd, then use list-ref to pick the middle element
3. If the length is even, use drop-list to drop the elements before the two middle elements, and then compute the average of the first two elements of the result.