2分探索

新人研修でのアルゴリズム演習から。

(defn find?
  ([lst v] (find? lst v 0 (dec (count lst))))
  ([lst v left-i right-i]
     (if (or (< v (lst left-i)) (< (lst right-i) v)) false
         (let [middle-i (+ (quot (- right-i left-i) 2) left-i)
               middle-v (lst middle-i)]
           (cond (= v middle-v) true
                 (< v middle-v) (recur lst v left-i (dec middle-i))
                 (> v middle-v) (recur lst v (inc middle-i) right-i))))))