lambdaway :: binary

8 | list | login |load

| |

_h1 binary search
_p Following [[https://rosettacode.org/wiki/Binary_search|https://rosettacode.org/wiki/Binary_search]]. This is the SCHEME code:

{pre

(define (binary-search value vector)
  (let helper ((low 0)
               (high (- (vector-length vector) 1)))
    (if (< high low)
        #f
        (let ((middle (quotient (+ low high) 2)))
          (cond ((> (vector-ref vector middle) value)
                 (helper low (- middle 1)))
                ((< (vector-ref vector middle) value)
                 (helper (+ middle 1) high))
                (else middle))))))

}

_p This is the '{lambda talk} code:

{pre
'{def BS 
 {def BS.r 
  {lambda {:a :v :i0 :i1}
   {let { {:a :a} {:v :v} {:i0 :i0} {:i1 :i1}
          {:m {floor {* {+ :i0 :i1} 0.5}}} } 
   {if {< :i1 :i0}
    then :v is not found
    else {if {> {A.get :m :a} :v}
    then {BS.r :a :v :i0 {- :m 1} }
    else {if {< {A.get :m :a} :v}
    then {BS.r :a :v {+ :m 1} :i1 }
    else :v is at array[:m] }}}}} }
 {lambda {:a :v}
  {BS.r :a :v 0 {- {A.length :a} 1}} }} 
-> {def BS 
 {def BS.r 
  {lambda {:a :v :i0 :i1}
   {let { {:a :a} {:v :v} {:i0 :i0} {:i1 :i1}
          {:m {floor {* {+ :i0 :i1} 0.5}}} } 
   {if {< :i1 :i0}
    then :v is not found
    else {if {> {A.get :m :a} :v}
    then {BS.r :a :v :i0 {- :m 1} }
    else {if {< {A.get :m :a} :v}
    then {BS.r :a :v {+ :m 1} :i1 }
    else :v is at array[:m] }}}}} }
 {lambda {:a :v}
  {BS.r :a :v 0 {- {A.length :a} 1}} }}
}

_p {b Note:} The {code let} special form is a syntaxic sugar for the call to an inner {code lambda}, see [[let]]. Because a {code lambda} doesn't create a closure, outer function's arguments must be duplicated/redefined in the {code let}'s arguments, hence {code '{:a :a} '{:v :v} '{:i0 :i0} '{:i1 :i1}}.

_p Testing:

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}
'{def A {A.new 12 14 16 18 20 22 25 27 30}}
-> {def A {A.new 12 14 16 18 20 22 25 27 30}} = {A}

'{BS {A} -1}  -> {BS {A} -1}
'{BS {A} 24}  -> {BS {A} 24}
'{BS {A} 25}  -> {BS {A} 25}
'{BS {A} 123} -> {BS {A} 123}

'{def B {A.new {S.serie 1 100000 2}}} 
-> {def B {A.new {S.serie 1 100000 2}}} = [1,3,5,... 99997,99999]  // ~ 50,000 terms

'{BS {B} 100}   -> {BS {B} 100}
'{BS {B} 12345} -> {BS {B} 12345}    
}

_p Computed in about 40ms.

_p Added in [[Rosetta|https://rosettacode.org/wiki/Binary_search#Lambdatalk]].