search.clj

(ns search.core
  (:use clojure.test))
(defn binary-search 
  "binary search"
  [coll start end key]
  ^{:pre [(> start -1) (< end (count coll))]}
  (if (> start end)
    -1
    (let [mid (quot (+ start end) 2)
          mvalue (nth coll mid)]
      (cond
        (> mvalue key) (recur coll start (- mid 1) key)
        (< mvalue key) (recur coll (+ mid 1) end key)
        :else mid))))

(defn search 
  "search key in coll '( N(m+1) N(m+2)...N(n-1) N(m) N(0) N(1) N(2)...N(m-1) ) which reversed in the index of m
  return the index of key or -1"
  ^{:pre [(> (count coll) m) (pos? m)]}
  [coll m key]  
  (let [length (count coll)
        index (- length m 1)
        vindex (nth coll index)]
    (cond
      (> vindex key) (binary-search coll (inc index) (dec length) key)
      (< vindex key) (binary-search coll 0 index key)
      :else index)))

;test
(with-test
  (defn gen-mcoll [len m]
    (let [m-reverse (fn [coll,m]
                      (concat (nthrest coll (inc m))
                              (list (nth coll m))
                              (take  m coll)))]
      (m-reverse (range 0 len) m)))
  (is (= 1  (search (gen-mcoll 10 3) 3 5))) ;'(4 5 6 7 8 9 3 0 1 2)
  (is (= 0  (search (gen-mcoll 10 4) 4 5))) ;'(5 6 7 8 9 4 0 1 2 3)
  (is (= 9  (search (gen-mcoll 10 4) 4 3)))
  (is (= 5  (search (gen-mcoll 10 4) 4 4)))) (run-tests 'search.core)