gistfile1.txt

(defun my-bisect (arr val less-p-fun)
  ;; 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.
  (let ((left 0)
        (right (length arr)))
    ;; 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 the initial ARR[LEFT] is not already greater or equal to the VAL
           (not (funcall less-p-fun (aref arr 0) val)))
      (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))))))


(assert (= (my-bisect #(1 777) 1 #'<)
           0))
(assert (= (my-bisect #(1 9) 3 #'<)
           1))
(assert (= (my-bisect #(1 2 11 12) 0 #'<)
           0))
(assert (= (my-bisect #(1 2 11 12) 2 #'<)
           1))
(assert (= (my-bisect #(1 2 11 12) 3 #'<)
           2))
(assert (= (my-bisect #(1 2 11 12) 12 #'<)
           3))
(assert (= (my-bisect #(1 2 11 12) 15 #'<)
           4))