From: keyboard
Subject: Why my loop is endless?
Date: Mon, 06 Aug 2007 06:16:57 +0000
Message-ID: <1186381017.440825.108080@b79g2000hse.googlegroups.com>

Hi,

I'm practicing loop, here is the code for a binary search for a sorted
array.

(defun binary-search (key array)
  "search sorted ARRAY(numbers) for KEY"
  (let ((low 0)
	(high (length array)))
    (loop for middle = (floor (/ (+ high low) 2))
	  when (> 1 (- high low))
	  do
	  (if (> key (elt array middle))
	      (setf low middle)
	      (setf high middle)))
    (if (= key (elt array high))
	high
	(format t "~% ~A is not found in ~A ~%" key array))))

when I try
(binary-search 3 #(1 2 3 4 5 6 7))

It never returns.

Where is the mistake? Is it a better way there?

best regards,
keyboard

• Re: Why my loop is endless? keyboard
  • Re: Why my loop is endless? Zach Beane

From: keyboard
Subject: Re: Why my loop is endless?
Date: Mon, 06 Aug 2007 07:11:23 +0000
Message-ID: <1186384283.699321.230360@o61g2000hsh.googlegroups.com>

On 6 Aug., 14:16, keyboard <···········@gmail.com> wrote:
> Hi,
>
> I'm practicing loop, here is the code for a binary search for a sorted
> array.
>
> (defun binary-search (key array)
>   "search sorted ARRAY(numbers) for KEY"
>   (let ((low 0)
>         (high (length array)))
>     (loop for middle = (floor (/ (+ high low) 2))
>           when (> 1 (- high low))
>           do
>           (if (> key (elt array middle))
>               (setf low middle)
>               (setf high middle)))
>     (if (= key (elt array high))
>         high
>         (format t "~% ~A is not found in ~A ~%" key array))))
>
> when I try
> (binary-search 3 #(1 2 3 4 5 6 7))
>
> It never returns.
>
> Where is the mistake? Is it a better way there?
>
> best regards,
> keyboard

Fixed.

(defun binary-search (key array)
  "search sorted ARRAY(numbers) for KEY"
  (let ((low 0)
	(high (length array)))
    (loop for middle = (floor (/ (+ high low) 2))
	  while (> (- high low) 1)
	  do
	  (if (> key (elt array middle))
	      (setf low middle)
	      (setf high middle)))
    (if (= key (elt array high))
	high
	(format t "~% ~A is not found in ~A ~%" key array))))

mixed with WHEN and WHILE.

From: Zach Beane
Subject: Re: Why my loop is endless?
Date: Mon, 06 Aug 2007 11:16:50 +0000
Message-ID: <m3fy2wkj4t.fsf@unnamed.xach.com>

keyboard <···········@gmail.com> writes:

>     (loop for middle = (floor (/ (+ high low) 2))

FYI, FLOOR takes an optional divisor, so (floor (+ high low) 2) would
work here too.

Zach