(ns binary.core
  (:gen-class))
; wikipedia algorithm for binary search
; Given an array A of n elements with values or records A0 ... An‚àí1,
; and target value T
; Set L to 0 and R to n ‚àí 1.
; If L > R, the search terminates as unsuccessful.
; Set m (the position of the middle element) to the floor of (L + R)‚Ää/‚Ää2.
; If Am < T, set L to m + 1 and go to step 2.
; If Am > T, set R to m – 1 and go to step 2.
; Now Am = T, the search is done; return m.

(defn binary-search [nums num]
  (defn recursor [nums num low-index high-index]
    (let [middle-index (int (/ (+ low-index high-index) 2))
          test-num (get nums middle-index)]
      (cond
        ; if test case is bigger than target set low index to current middle + 1
        (< test-num num) (recursor nums num (+ middle-index 1) high-index)
        ; if test case is lower than target set high-index to current middle index - 1
        (> test-num num) (recursor nums num low-index (- middle-index 1))
        ; otherwise you have a match
        :else middle-index)))
  (let [low-index 0
        high-index (- (count nums) 1)]
    (if (or (> low-index high-index) (< num low-index) (> num high-index))
      (throw (Exception. "Search outside of bounds"))
      (recursor nums num low-index high-index))))

(defn -main
  "Naive recursive binary search in clojure"
  [& args]
  (def nums [0 1 2 3 4 5 6 7 8 9 10])
  (println (binary-search nums 10)))