gistfile1.txt

(defun my-bisect (arr val less-p-fun)
  (let ((left 0)
        (right (length arr)))
    ;; Returns  a position right past all elements lesser than the val.
    ;; The position may be within the array bounds, or may be the (length arr)
    ;; if all elements are less then the val, or the array is empty.
    ;;
    ;; Invariant1: arr[left] < val
    ;; Invariant2: All elements less then the val are below the right.
    ;;
    ;; The invariant2 already holds (as whole array is below the right)
    ;;
    ;; For the invariant1 we must ensure that:
    (when (or
           ;; our initial left=0 is in range
           (zerop (length arr))
           ;; and arr[lert] is not already greater than the val
           (funcall less-p-fun val (aref arr 0)))
      (return-from my-bisect 0))
    
    (loop
      (let ((mid (floor (/ (+ left right) 2))))
        (when (= mid left)
          ;; means left + 1 = right,
          ;; and so RIGHT is the solution
          ;; given the invariants
          (return right))
        (if (funcall less-p-fun (aref arr mid) val)
            ;; adjust left, still invariant1 remains true
            (setq left mid)
            ;; adjust right, still invariant2 remains true
            (setq right mid))))))


(my-bisect #(1 9) 3 #'<)
;; => 1

(my-bisect #(1 2 11 12) 0 #'<)
;; => 0
(my-bisect #(1 2 11 12) 2 #'<)
;; => 1
(my-bisect #(1 2 11 12) 3 #'<)
;; => 2
(my-bisect #(1 2 11 12) 12 #'<)
;; => 3
(my-bisect #(1 2 11 12) 15 #'<)
;; => 4