ericnormand/00 binary search.md

## 00 binary search.md

      
    Raw
  

              00 binary search.md
            
          
    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.

  
## Björn Steffen.clj
(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)

## Charlie Mead.clj
(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)))))))

## Frank Adrian.clj
(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))))))

## Jaihindh Reddy.clj
(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)))))))

## Mark Champine.clj
(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)))))

## Nathan Donolli.clj
(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)))))))

## Neil McCallum.clj
(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))))))

## Paul Roush.clj
;; 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)))))

## Steffan Westcott.clj
(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)))

## Viktor P.clj
(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))))))))
	(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))))))))