全探索と二分探索

全探索

search.scm

(define (binarysearch lst n)
  (let loop ((lst lst))
    (receive(left right)
      (split-at lst (div (length lst) 2))
        (cond ((null? left)#f)
              ((null? right)#f)
              ((eq? (last left) n)#t)
              ((eq? (car right) n)#t)
              ((> (last left) n)(loop left))
              ((< (car right) n)(loop right)))))))

二分探索

binarysearch.scm

(define (binarysearch lst n)
  (let loop ((lst lst))
    (receive(left right)
      (split-at lst (div (length lst) 2))
        (cond ((null? left)#f)
              ((null? right)#f)
              ((eq? (last left) n)#t)
              ((eq? (car right) n)#t)
              ((> (last left) n)(loop left))
              ((< (car right) n)(loop right))))))

結果

(1 3 5 11 12 13 17 22 25 28)から25を探索するとき

全探索

(1 3 5 11 12 13 17 22 25 28)
(3 5 11 12 13 17 22 25 28)
(5 11 12 13 17 22 25 28)
(11 12 13 17 22 25 28)
(12 13 17 22 25 28)
(13 17 22 25 28)
(17 22 25 28)
(22 25 28)
(25 28)

二分探索

(1 3 5 11 12):(13 17 22 25 28)
(13 17):(22 25 28)
(22):(25 28)

二分探索のほうが圧倒時に…はい