Are you one of the 10% of competent programmers?


#1

I recently discovered this article on Colin Wright’s blog about using Binary Search as an interesting test problem: Binary Search Reconsidered.

The algorithm is:

You’re looking for an item in a sorted list, so you look in the middle. If the thing you find is bigger than what you’re looking for, then the item - if it’s there at all - must be in the first half, otherwise it’s in the second half. Repeat until you either find the item, or there are no items left in which case the item is not in the list.

In his book Programming Pearls Jon Bentley wrote that he assigned this problem in courses at Bell Labs and IBM. Professional programmers had a couple of hours to convert the above description into a program in the language of their choice.

At the end of the specified time, almost all the programmers reported that they had correct code for the task … but on testing their code 90% of the programmers found bugs in their programs.

Try writing a program in Lisp to do this. If the number is in the list it should return t:

>  (binary-search 5 '(0 1 2 3 5 5 6 7 8 9 10))
t

If the number isn’t in the list it should return nil:

> (binary-search 4 '(0 1 2 3 5 5 6 7 8 9 10))
nil

You’re not allowed to test the program until you’ve finished it.

I wrote my program in uLisp, but I have to admit that my program had a silly mistake so I’m in the 90%. I’ll reveal my answer in this thread in a day or so.

See how well you get on!


#2

Very nice excercise. Thanks.
Had to break out of an infinite loop on the first try… :^)

An idea would be to restate the problem to search an array, because it feels wrong to use lists for this.
Even checking the size of the list is already traversing the whole list, and a simple (member n lst) would outperform the binary search when using lists.
Using arrays we can really show off both the beauty and speed of Lisp.

But still a very good brain-teaser.
And thanks for uLisp.


#3

Yes, good point about lists vs. arrays. I did it using lists and that made it a lot easier.


#4

Hmm, that makes me very curious about your solution.
In my solution, the only difference between using list and array is changing nth to aref.

Just had to tweak it to support both lists and arrays. ;)
Works in both uLisp and Common Lisp.

Would you like us to post solutions? Or maybe wait a while?


#7

Here’s my solution to the Binary Search algorithm, in uLisp:

(defun binary-search (item lst)
  (cond
   ((null lst) nil)
   (t (let* ((index (truncate (length lst) 2))
             (mid (nth index lst)))
        (cond
         ((= item mid) t)
         ((< item mid) (binary-search item (subseq* lst 0 index)))
         (t (binary-search item (subseq* lst (1+ index)))))))))

(defun subseq* (lst n &optional (m (length lst)))
  (cond
   ((> n 0) (subseq* (cdr lst) (1- n) (1- m)))
   ((zerop m) nil)
   (t (cons (car lst) (subseq* (cdr lst) 0 (1- m))))))

If it hasn’t found the item it recursively calls binary-search on the first half of the list, or the second half of the list, depending on whether the item is less than or greater than the middle element of the list.

In uLisp subseq doesn’t work with lists, so I’ve defined my own version of subseq called subseq*. In Common Lisp you can just use subseq.

I look forward to seeing what other solutions anyone has come up with!


#8

90%, unfortunately… and my godawefully ugly solution, merely to satisfy the description but without any regard to optimization (just called it “ispresent”):

(defun ispresent (x srtl)
  (cond
   ((null srtl) nil)
   ((null (cdr srtl)) (equal (car srtl) x))
   (t (let ((lensrtl (length srtl)))
        (let ((halflen (floor (/ lensrtl 2))))
          (let ((firsthalf (reverse (nthcdr halflen (reverse srtl))))
                (secondhalf (nthcdr (- lensrtl halflen) srtl)))
            (cond
             ((or (equal (car (last firsthalf)) x) (equal (car secondhalf) x)) t)
             (t (or (ispresent x firsthalf) (ispresent x secondhalf))))))))))

#9

It seems to work OK! Note that it needs a few extra definitions to work in uLisp.


#11

Another 90%-er… :-\

(defun binary-search (x sortl)
    (let ((bsrch (lambda (num start end)
		(let ((mid (+ start (floor (- end start) 2))))
		    (cond
			   ((> start end)			nil)
			   ((= num (nth mid sortl))	t)
			   ((< num (nth mid sortl))	(bsrch num start (- mid 1)))
			   (t				(bsrch num (+ mid 1) end))
		    )))))
     (bsrch x 0 (- (length sortl) 1))
))

#12

Hello,

Just for fun I asked chatGPT:

best regards


#13

Here is an iterative implementation similar to what one might write in an imperative language.

(defun binary-search (n lst)
  (let*
      ((f 0)
       (b (1- (length lst))))
    (loop
     (when (> f b) (return nil))
     (let*
         ((c (truncate (+ f b) 2))
          (v (nth c lst)))
       (cond
         ((= n v) (return t))
         ((< n v) (setq b (1- c)))
         (t       (setq f (1+ c))))))))

Assuming it’s working, which I wouldn’t bet either way, it worked “first time.” Full disclosure: I read Bentley’s Programming Pearls books years ago and have implemented the algorithm a few times in other languages.