Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Last active December 11, 2020 16:43
Show Gist options
  • Save ericnormand/892bcb31280859727c2375c7d41bea81 to your computer and use it in GitHub Desktop.
Save ericnormand/892bcb31280859727c2375c7d41bea81 to your computer and use it in GitHub Desktop.

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.

(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)
(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)))))))
(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))))))
(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)))))))
(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)))))
(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)))))))
(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))))))
;; 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)))))
(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)))
(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
Copy link

(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))))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment