バイナリサーチ

(defun kv (key val)
  (cons key val))

(defun make-table (&rest kv-pairs)
  (make-array (length kv-pairs)
              :initial-contents kv-pairs))

(defun aridx1 (array idx)
  (aref array (1- idx)))

(defun bin-search (key table)
  (let ((lo 1)
        (hi (length table)))
    (loop while (<= lo hi)
          do
          (let ((mid (ash (+ lo hi) -1)))
            (format t "lo: ~A hi: ~A mid: ~A~%" lo hi mid)
            (when (<= key (car (aridx1 table mid)))
              (setf hi (1- mid)))
            (when (>= key (car (aridx1 table mid)))
              (setf lo (1+ mid)))))
    (if (= lo (+ hi 2))
      (values t (1- lo))
      nil)))

(defun %bin-search (key table)
  (let ((lo 1)
        (hi (length table)))
    (loop while (<= lo hi)
          do
          (let ((mid (ash (+ lo hi) -1)))
            (format t "lo: ~A hi: ~A mid: ~A~%" lo hi mid)
            (if (< key (car (aridx1 table mid)))
              (setf hi (1- mid))
              (setf lo (1+ mid)))))
    (if (zerop hi)
      nil
      (values (= key (car (aridx1 table hi))) hi))))