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