I thought I would get an email when there was something happening in this thread, but nothing, so a bit late with my contribution…

Anyway, I really like your very Lispy recursive solution. Beauty.

It also makes interesting patterns when both functions are traced with a proper input length.

And it’s much faster than I thought it would be, even when tracing. I’m using Pico W’s.

#### My uLisp solutions, one looping and one recursive - that also work in Common Lisp - handle both arrays and lists:

```
(defun binary-search (num seq)
"Loopy - array or list"
(let ((lo 0)
(hi (1- (length seq))))
(loop
(when (< hi lo) (return))
(let* ((pos (ash (+ lo hi) -1))
(val (if (listp seq) (nth pos seq) (aref seq pos))))
(cond
((< num val) (setf hi (1- pos)))
((> num val) (setf lo (1+ pos)))
(t (return t)))))))
```

```
(defun binary-search (num seq &optional lo hi)
"Recursive - array or list"
(if (null lo)
(binary-search num seq 0 (1- (length seq)))
(when (<= lo hi)
(let* ((pos (ash (+ lo hi) -1))
(val (if (listp seq) (nth pos seq) (aref seq pos))))
(cond ((< num val) (binary-search num seq lo (1- pos)))
((> num val) (binary-search num seq (1+ pos) hi))
(t))))))
```

Also made some helper functions for testing that work both in uLisp and Common Lisp:

```
(defun fill-array (n &optional skip)
(let ((v (make-array n)))
(dotimes (i n v)
(setf (aref v i) (if (eq i skip) (1+ i) i)))))
(defvar vt (fill-array 10 4))
(defvar vf (fill-array 50 4))
(defvar vh (fill-array 100 4))
```

```
(defun fill-list (n &optional skip)
(let (l)
(reverse
(dotimes (i n l)
(push (if (eq i skip) (1+ i) i) l)))))
(defvar lt (fill-list 10 4))
(defvar lf (fill-list 50 4))
(defvar lh (fill-list 100 4))
```

I was also playing with the idea of recursively splitting the input, like you did, because that felt like the naturally Lispy way, but only did that solution for arrays in **Clojure**:

```
(defn binary-search [num v]
"Search for num in array v"
(let [cnt (count v)]
(when (pos? cnt)
(let [pos (bit-shift-right cnt 1)
val (v pos)]
(cond (< num val) (recur num (subvec v 0 pos))
(> num val) (recur num (subvec v (inc pos)))
:else true)))))
```

Nice exercise.

Thanks.