;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname review_1) (read-case-sensitive #t) (teachpacks ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp") (lib "batch-io.rkt" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp") (lib "batch-io.rkt" "teachpack" "2htdp")) #f)))
#| Topics:
Code detective
Trees
generative recursion
accumulator recursion
foldr, foldl, map, filter, build-list, etc.
Everything from first exam
s-expressions
|#


#|
Idea: Cut the list in half every time we compare an element to a number
instead of searching the whole list
Looking for 3 in the below list:
1 24 568 9860 9981 9999 19999 199999 1999999 19999999 199999999 || 3 < 9999
                   ^middle
1 24 568 9860 9981 || 3 < 568
     ^middle
1 24 || 3 > 1
^"middle" (if we use floor)
24 || 3 < 24
^middle
|| 3 does not appear|#
;; Binary search: on a sorted list
;; binary-search: [Listof Int] Int -> Int
(define (binary-search l num)
  (local (;; min=smallest index that could contain the item
          ;; max=biggest index that could contain the item
          (define (f min max)
            (local ((define mid (floor (/ (+ max min) 2))))
              (cond [(< max min) -1]
                    [(= num (list-ref l mid)) mid]
                    [(< num (list-ref l mid)) (f min (sub1 mid))]
                    [else (f (add1 mid) max)]))))
    (f 0 (sub1 (length l)))))
(check-expect (binary-search '(1 2 3 45 60) 45) 3)
(check-expect (binary-search '(1 2 3 45 60) 70) -1)
(check-expect (binary-search empty 70) -1)

(define-struct bt (l r))
;; A BT is one of:
;; 'leaf
;; (make-bt BT BT)
;; biggest-height : [Nonempty-Listof BT] -> BT
;; Find tree with the biggest height
(define (biggest-height lbt)
  (local ((define (bt-height bt)
            (cond [(symbol? bt) 0]
                  [else (add1 (max (bt-height (bt-l bt))
                                   (bt-height (bt-r bt))))]))
          ;; biggest=biggest tree seen so far
          ;; height=(bt-height biggest)
          ;; list=trees yet to be checked
          (define (loop biggest height list)
            (cond [(empty? list) biggest]
                  [(> (bt-height (first list)) height)
                   (loop (first list) (bt-height (first list)) (rest list))]
                  [else (loop biggest height (rest list))])))
    (loop (first lbt) (bt-height (first lbt)) (rest lbt))))

;; alternate solution - without loop/accumulators
;; possibly computes height on the same tree many times!
#;(foldr (lambda (some-tree biggest-so-far)
           (if (> (bt-height some-tree) (bt-height biggest-so-far))
               some-tree
               biggest-so-far))
         (first lbt) (rest lbt))