{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 binary search.md

Last active Dec 11, 2020

Binary search

If I give you a sorted vector of integers, you can search through it quickly using binary search to know if it contains a given number `n`. Is `n` right in the middle? If yes, you're done. If not, then you either have to search the left half or the right half. Since the numbers are sorted, you can check if `n` is greater than or less than the middle number. You can then recurse down into the appropriate half. Your task is to write this function.

```(binary-search 3 [1 2 3]) ;=> true
(binary-search 4 [1 2 5]) ;=> false
(binary-search 10 [1 2 4 5 9 10 11 12]) ;=> true```

You can assume you're passed a sorted vector.

Thanks to this site for the challenge idea where it is considered Hard level in Python.

Email submissions to eric@purelyfunctional.tv before August 29, 2020. You can discuss the submissions in the comments below.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (use 'clojure.test) (defn binary-search [val vec] (let [index (int (/ (count vec) 2)) v (get vec index)] (cond (nil? v) false (= val v) true (< val v) (recur val (subvec vec 0 index)) (> val v) (recur val (subvec vec (inc index)))))) (deftest bs (is (= true (binary-search 3 [1 2 3]))) (is (= false (binary-search 4 [1 2 5]))) (is (= true (binary-search 10 [1 2 4 5 9 10 11 12]))) (is (= false (binary-search 4 [])))) (run-tests)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [x xs] (loop [left 0 right (- (count xs) 1)] (let [mid (Math/round (double (/ (+ left right) 2)))] (if (> left right) false (let [val (get xs mid)] (cond (= val x) true (> val x) (recur left (- mid 1)) (< val x) (recur (+ mid 1) right)))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [tgt ar] (loop [ar ar] (let [cnt (count ar) med (quot cnt 2) tst (get ar med)] (cond (= 0 cnt) false (= 1 cnt) (= tgt (get ar 0)) (= tgt tst) true (< tgt tst) (recur (subvec ar 0 med)) :else (recur (subvec ar med))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [x coll] (loop [coll coll] (if (empty? coll) false (let [m (quot (count coll) 2)] (case (compare x (nth coll m)) 0 true 1 (recur (subvec coll (inc m))) -1 (recur (subvec coll 0 m)))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [n sc] (loop [seg sc] (let [[lc hc] (split-at (/ (count seg) 2) seg)] (cond (not (<= (first seg) n (last seg))) false (= n (last seg)) true (>= (last lc) n) (recur lc) :else (recur hc)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [target coll] (loop [tree coll] (let [idx (int (/ (count tree) 2)) node (nth tree idx)] (cond (= target node) true (= 1 (count tree)) false (< target node) (recur (subvec tree 0 idx)) (> target node) (recur (subvec tree idx (count tree)))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [goal col] (loop [min 0 max (dec (count col))] (if (= min max) (= goal (nth col min)) (let [mid-idx (quot (+ min max) 2) item (nth col mid-idx)] (cond (= goal item) (recur mid-idx mid-idx) (< goal item) (recur min (dec mid-idx)) (> goal item) (recur (inc mid-idx) max))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; Is 'n' contained in sorted vector 'v' ? (defn binary-search [n v] (let [avg (fn [& xs] (/ (reduce + xs) (count xs))) search (fn [v n lo-idx hi-idx] (let [mid-idx (avg lo-idx hi-idx) [lo mid hi] (map (partial nth v) [lo-idx mid-idx hi-idx])] (cond (< n lo) false (> n hi) false (= n mid) true (< n mid) (recur v n lo-idx (dec mid-idx)) (> n mid) (recur v n (inc mid-idx) hi-idx))))] (search v n 0 (dec (count v)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [x xs] (loop [start 0 end (count xs)] (if (< start end) (let [mid (quot (+ start end) 2) cmp (compare x (nth xs mid))] (cond (neg? cmp) (recur start mid) ;; exclude middle element (pos? cmp) (recur (inc mid) end) ;; exclude middle element :else true)) false)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn binary-search [n numbers] (if (not (seq numbers)) false (let [mid-idx (int (/ (count numbers) 2)) mid-val (nth numbers mid-idx)] (or (= n mid-val) (binary-search n (if (< n mid-val) (subvec numbers 0 mid-idx) (subvec numbers (inc mid-idx))))))))

### KingCode commented Dec 11, 2020

``````(defn binary-search [search from]
(let [mid (-> (count from) (/ 2) int)
v (get from mid)]
(cond
(not v)      false
(= v search) true
(< search v) (recur search (subvec from 0 mid))
:else        (recur search (subvec from (inc mid))))))
``````