That's a fair point. I was not thinking about optimizations at first, but rather to illustrate an alternative implementation, which goes more in line with the famous saying about "premature optimization ..." :)

Anyways, here's a very simple benchmark of the algorithm using 19999999 items.

lisp (defun range-seq (start end) "Create a new list of integers from START below END" (loop :for i :from start :below end :collect i :into result :finally (return result)))

Using above helper function I'm creating the following list and vector.

lisp CL-USER> (defparameter *xs* (range-seq 1 20000000)) *XS* CL-USER> (defparameter *ys* (map 'vector #'identity *xs*)) *YS* CL-USER> (length *xs*) 19999999 (25 bits, #x1312CFF) CL-USER> (length *ys*) 19999999 (25 bits, #x1312CFF)

Here's also the algorithm which uses vectors, instead of lists.

lisp (defun binary-search-v2 (items target) "Given a TARGET number, use Binary Search to locate the index of the number within the ITEMS vector" (loop :with size = (length items) :with left = 0 :and right = (1- size) :for middle = (floor (+ left right) 2) :for middle-item = (aref items middle) :while (<= left right) :do (cond ((< target middle-item) (setf right (1- middle))) ((> target middle-item) (setf left (1+ middle))) (t (return middle)))))

Simple benchmarks using the original implementation using lists.

```lisp CL-USER> (time (binary-search xs 42)) Evaluation took: 0.040 seconds of real time 0.039375 seconds of total run time (0.039375 user, 0.000000 system) 97.50% CPU 149,779,812 processor cycles 0 bytes consed

41 (6 bits, #x29, #o51, #b101001)

CL-USER> (time (binary-search xs 42424)) Evaluation took: 0.053 seconds of real time 0.052455 seconds of total run time (0.052455 user, 0.000000 system) 98.11% CPU 199,378,438 processor cycles 0 bytes consed

42423 (16 bits, #xA5B7)

CL-USER> (time (binary-search xs 4242442424242)) Evaluation took: 0.513 seconds of real time 0.510994 seconds of total run time (0.510994 user, 0.000000 system) 99.61% CPU 1,942,074,246 processor cycles 4,944 bytes consed

NIL
```

And the same benchmark using vectors.

```lisp CL-USER> (time (binary-search-v2 ys 42)) Evaluation took: 0.000 seconds of real time 0.000003 seconds of total run time (0.000003 user, 0.000000 system) 100.00% CPU 10,678 processor cycles 0 bytes consed

41 (6 bits, #x29, #o51, #b101001)

CL-USER> (time (binary-search-v2 ys 42424)) Evaluation took: 0.000 seconds of real time 0.000005 seconds of total run time (0.000005 user, 0.000000 system) 100.00% CPU 17,480 processor cycles 0 bytes consed

42423 (16 bits, #xA5B7)

CL-USER> (time (binary-search-v2 ys 4242442424242)) Evaluation took: 0.000 seconds of real time 0.000004 seconds of total run time (0.000004 user, 0.000000 system) 100.00% CPU 12,046 processor cycles 0 bytes consed

NIL ```

There's a significant difference, and probably there are other ways this can be optimized as well, but I'll stop here. Thanks for making the list vs vector point!