Function: VECTOR-SEARCH

Documentation

- uses binary search to find the index of key in vector. - vector must be sorted - returns : (nil index) if key not found and search stoped at index (index index) if key was found

Source

(defun vector-search (key vector &key (key-fn #'identity) (start 0)
		      (end (1- (length vector)))
		      (comparator (number-comparator)))
  "- uses binary search to find the index of key in vector.
   - vector must be sorted
   - returns : (nil index) if key not found and search stoped at index
               (index index) if key was found"
  (let* ((mid (round (+ start end) 2))
	 (k (funcall key-fn (aref vector mid))))
    (cond ((comp-= key k comparator) (values mid mid))
	  ((<= end start) (values nil start))
	  (t (let ((left (if (comp-< key k comparator)
			     start
			     (if (= start mid) end mid)))
		   (right (if (comp-> key k comparator)
			      end
			      (if (= end mid) start mid))))
	       (vector-search key vector :key-fn key-fn
			      :start left :end right
			      :comparator comparator))))))