4.2 示例：二叉搜索 (Example: Binary Search)

作为一个示例，这小节演示如何写一个在排序好的向量里搜索对象的函数。如果我们知道一个向量是排序好的，我们可以比（65页） find 做的更好， find 必须依序检查每一个元素。我们可以直接跳到向量中间开始找。如果中间的元素是我们要找的对象，搜索完毕。要不然我们持续往左半部或往右半部搜索，取决于对象是小于或大于中间的元素。

图 4.1 包含了一个这么工作的函数。其实这两个函数： bin-search 设置初始范围及发送控制信号给 finder ， finder 寻找向量 vec 内 obj 是否介于 start 及 end 之间。

  1. (defun bin-search (obj vec)
  2.   (let ((len (length vec)))
  3.     (and (not (zerop len))
  4.          (finder obj vec 0 (- len 1)))))
  6. (defun finder (obj vec start end)
  7.   (let ((range (- end start)))
  8.     (if (zerop range)
  9.         (if (eql obj (aref vec start))
  10.             obj
  11.             nil)
  12.         (let ((mid (+ start (round (/ range 2)))))
  13.           (let ((obj2 (aref vec mid)))
  14.             (if (< obj obj2)
  15.                 (finder obj vec start (- mid 1))
  16.                 (if (> obj obj2)
  17.                     (finder obj vec (+ mid 1) end)
  18.                     obj)))))))

图 4.1: 搜索一个排序好的向量

如果要找的 range 缩小至一个元素，而如果这个元素是 obj 的话，则 finder 直接返回这个元素，反之返回 nil 。如果 range 大于 1 ，我们設置 middle ( round 返回离实参最近的整数) 為 obj2 。如果 obj 小于 obj2 ，则递归地往向量的左半部寻找。如果 obj 大于 obj2 ，则递归地往向量的右半部寻找。剩下的一个选择是 obj=obj2 ，在这个情况我们找到要找的元素，直接返回这个元素。

如果我们插入下面这行至 finder 的起始处：

  1. (format t "~A~%" (subseq vec start (+ end 1)))

我们可以观察被搜索的元素的数量，是每一步往左减半的：

  1. > (bin-search 3 #(0 1 2 3 4 5 6 7 8 9))
  2. #(0 1 2 3 4 5 6 7 8 9)
  3. #(0 1 2 3)
  4. #(3)
  5. 3