二分搜索 (Binary search)

问题

在有序序列 [min, max] 中搜索 key 值

思路

取 mid = (min + max) / 2
key 等于 [mid], 找到最终解
key 大于 [mid], 那么原问题变为：在有序序列 [mid+1, max] 中搜索 key 值
key 不大于 [mid], 那么原问题变为：在有序序列 [min, mid-1] 中搜索 key 值

代码

(define (binary-search vec key min max)
  (if (> min max)
      -1
      (let ((mid (quotient (+ min max) 2)))
        (if (= key (vector-ref vec mid))
            mid
            (if (> key (vector-ref vec mid))
                (binary-search vec key (+ mid 1) max)
                (binary-search vec key min (- mid 1)))))))