codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; find x[i] = i in an array (define x (vector -3 -1 0 3 5 7)) (define y (vector -3 -1 0 2 5 7)) (define (f x) (let loop ((i 0)) (cond ((= i (vector-length x)) -1) ; not present ((= i (vector-ref x i)) i) ; found solution (else (loop (+ i 1)))))) ; try next element (display (f x)) (newline) (display (f y)) (newline) (define (f x) (let loop ((lo 0) (hi (- (vector-length x) 1))) (if (< hi lo) -1 ; not present (let ((mid (quotient (+ lo hi) 2))) (cond ((< (vector-ref x mid) mid) (loop (+ mid 1) hi)) ((< mid (vector-ref x mid)) (loop lo (- mid 1))) (else mid)))))) ; found solution (display (f x)) (newline) (display (f y)) (newline)
Private
[
?
]
Run code
Submit