;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; lst is a list consisited of elements with distinct values
; key is the target value we are going to search
;
; if a search is found, return #t, else return #f
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define binary-search
  (lambda (lst key)
    (cond
      ( (null? key) #f)
      ( (null? lst) #f)
      ( (< (median lst) key) (binary-search (trim-start lst (median lst)) key))
      ( (> (median lst) key) (binary-search (trim-end lst (median lst)) key))
      ( else #t )
     );end cond
    );end lambda
  );end define

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; lst is a list consisted of elements with dinstinct values
; end is the value of the element which we start omitting from
;
; return a copy of list up to end-1, with rest of the elements omitted (including end)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define trim-end
  (lambda (lst end)
      (cond
        ( (null? end) lst)
        ( (null? lst) lst)
        ( (equal? (car lst) end) '())
        ( else (cons (car lst) (trim-end (cdr lst) end)))
        );end cond
    );end lambda
  );end define

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; lst is a list consisted of elements with dinstinct values
; start is the value of the element which we stop omitting at
;
; return a copy of list from start+1, with leading elements omitted (including start)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define trim-start
  (lambda (lst start)
    (cond
      ( (null? start) lst)
      ( (null? lst) lst)
      ( (equal? (car lst) start) (cdr lst))
      ( else (trim-start (cdr lst) start))
     );end cond
    );end lambda
  );end define

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; lst is a list consisted of elements with dinstinct values
;
; return the median element in the list
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define median
  (lambda (lst)
    (cond
      ( (null? lst) '())
      ( (or (equal? (length lst) 2) (equal? (length lst) 1))
        (car lst) )
      ( else (median (remove-last (cdr lst))) )
      );end cond
    );end lambda
  );end define

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; lst is a list consisted of elements with dinstinct values
;
; return the copy of the list with the last element removed.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define remove-last
  (lambda (lst) ; lst is not empty, and has n distinct elements
    (cond
      ( (null? lst) '())
      ( (equal? (length lst) 1) '() )
      ( else (cons (car lst) (remove-last(cdr lst))) )
     );end cond
    );end lambda
  );end define