Emanuele wrote:Sorry @tufty, maybe I was a bit too confrontational.

Not at all. I certainly didn't take it that way, anyway, and even if I had, I wouldn't have taken it personally. Flame away, I can take it :)

I'm absolutely with you on teaching concrete problems as well, but they are, at least if we're talking about fundamentals, secondary to teaching the structural patterns, the algorithms needed. As such, looking at different possible implementations of something like binary search is incredibly important, and a very valuable teaching tool. There's pretty much 2 ways to go about it - iteratively and recursively (although I'll show a third option and blow Burngate's mind a little further later in this post), and they pretty much come down to the same thing:

Split your dataset down the middle, extract the middle value, if it's the value we're looking for return it, otherwise repeat using either the "left" or "right" part of the dataset depending on the value in the middle. The only difference is how we go about doing the "repeat" bit, but the difference is largely syntactic (assuming a language that handles tail recursion) and the two approaches are fundamentally identical.

Here's a BBC BASIC version of the same thing, pulled shamelessly from (google's cache of) rosettacode.org. What you'll notice is that the pattern, described above, is hopelessly mixed with the implementation details (in this case, the use of signed 32 bit variables in a single-dimensioned array); reimplementing to use (for example) fixed length strings or arbitrary structures contained in some other container type (if BASIC even permits such an approach) means rewriting the whole thing. It's also longer, both line for line and expression for expression, than the more generic scheme version (my friend Burngate's comprehension notwithstanding).

Code: Select all

```
REM Search ordered array A%() for the value S% from index B% to T%
DEF FNwhere(A%(), S%, B%, T%)
LOCAL H%
H% = 2
WHILE H%<(T%-B%) H% *= 2:ENDWHILE
H% /= 2
REPEAT
IF (B%+H%)<=T% IF S%>=A%(B%+H%) B% += H%
H% /= 2
UNTIL H%=0
IF S%=A%(B%) THEN = B% ELSE = -1
```

It's all swings and roundabouts, though, really.

For those as what don't read scheme much, here's a non-generic scheme version looking for numbers in a vector, with comments

Code: Select all

```
;; Define a function named bsearch taking two arguments, val and vec
(define (bsearch val vec)
;; Define a recursion point named loop (which can be used as a function later) taking two arguments, start and stop, with initial values
(let loop ([start 0] [end (- (vector-length vec) 1)])
;; Check for "not found" condition, where 'end' is less than 'start', return false if so
(if (< end start) #f
;; Introduce 2 new variables, the midpoint (from an integer division of (start + end) by 2) and the value at that location in the vector.
(let* ([mid (quotient (+ start end) 2)] [mid-val (vector-ref vec mid)])
(cond [(= val mid-val) mid] ;; If we've found it, return the index
[(< val mid-val) (loop (+ mid 1) end)] ;; If we're "to the left", recurse with the right hand side of start->mid->end
[else (loop start (- mid 1))])))) ;; otherwise recurse with the left hand side of start->mid->end
```

And, for Burngate's amusement, the same thing (mechanically, and perhaps incorrectly, as my cps-converter is not fully war-tested) converted into

continuation passing style. Warning - it might be

*marginally* less readable than the other versions presented.

Code: Select all

```
(define bsearch
(lambda (val vec k-2)
(letrec ([mid (lambda (s e k-20)
(+/k
s
e
(lambda ($rv-21) (quotient/k $rv-21 2 k-20))))]
[loop (lambda (start end k-5)
(</k end
start
(lambda
($rv-6)
(mid start
end
(lambda
($rv-19)
(vector-ref/k
vec
$rv-19
(lambda
($rv-18)
(=/k val
$rv-18
(lambda
($rv-17)
(if $rv-17
(lambda
($rv-7)
(mid start
end
(lambda
($rv-8)
(mid start
end
(lambda
($rv-16)
(vector-ref/k
vec
$rv-16
(lambda
($rv-15)
(</k val
$rv-15
(lambda
($rv-10)
(if $rv-10
(mid start
end
(lambda
($rv-14)
(+/k
$rv-14
1
(lambda
($rv-13)
(loop
$rv-13
end
(lambda
($rv-9)
(if $rv-6
#f
$rv-7
$rv-8
$rv-9
k-5)))))))
(mid start
end
(lambda
($rv-12)
(-/k
$rv-12
1
(lambda
($rv-11)
(loop
start
$rv-11
(lambda
($rv-9)
(if $rv-6
#f
$rv-7
$rv-8
$rv-9
k-5)))))))))))))))))))))))))))])
(vector-length/k
vec
(lambda
($rv-4)
(-/k $rv-4 1 (lambda ($rv-3) (loop 0 $rv-3 k-2)))))))
(lambda ($rv-1) ($rv-1 (lambda ($rv-0) (letrec $rv-0 halt)))))
```