Challenge - Binary Search

Binary search

Given an array of numbers sorted in ascending order, find the position (index) of a number. Return -1 if the number is not in the array.

Solution in Clojure language:


(defn search
  "Find the index of a number in a sorted vector"
  ([numbers target]
   (println "Searching" target "in" numbers)
   (search numbers target 0 (count numbers)))
  ([numbers target low high]
   (if (= low high)
     -1
     (let [mid (quot (+ low high) 2)
           guess (nth numbers mid)]
       (cond
         (> guess target) (search numbers target low mid)
         (< guess target) (search numbers target (inc mid) high)
         :else mid)))))

(do
  (println (search [-1 0 3 5 9 12] 9))  ; 4
  (println (search [-1 0 3 5 9 12] 2))  ; -1
  (println (search [-1 0 3 5 9 12 17] 17))  ; 6
  (println (search [-1 0 3 5 9 12 17] -1))  ; 0
  (println (search (range 100) (rand-int 150))))

How it works:

The principle of binary search is to cut the range in half with every step.
This way it is very quick to search even in large arrays (it takes about 20 steps for 1 million elements).
The first range goes from 0 to the size of the array.
Every time we calculate the middle point of the range, and check the array element at that index.
If it is bigger than the value we're looking for, continue the search in the lower half.
If it is smaller than the target, continue the search in the upper half.
If it is a match, then mission complete.
If we reduce the search range so that the low and high end are the same, and we still haven't found the value, then it is not in the array.

[clj] binary search