;; vec-search-down? : (any -> boolean) (vectorof any) -> boolean
;; Purpose: Returns whether any element of the vector meets the given
;;          predicate.
;; Examples:
;;   (vec-search-down? number? (vector true false)   = false
;;   (vec-search-down? number? (vector true 3 false) = true
;;   (vec-search-down? number? (vector)              = false

(define (vec-search-down1? pred? a-vec)
  (local [;; search : natnum -> boolean
	  ;; Purpose: Returns whether any element 0..position-1 of a-vec
	  ;;          meets predicate pred?.
	  (define (search position)
	    (cond
	      [(zero? position)
	       false]
	      [else
		(or (pred? (vector-ref a-vec (sub1 position)))
		    (search (sub1 position)))]))]
    (search (vector-length a-vec))))

(define (vec-search-down2? pred? a-vec)
  (local [;; search : natnum -> boolean
	  ;; Purpose: Returns whether any element 0..position of a-vec
	  ;;          meets predicate pred?.
	  (define (search position)
	    (cond
	      [(zero? position)
	       (pred? (vector-ref a-vec position))]
	      [else
		(or (pred? (vector-ref a-vec position))
		    (search (sub1 position)))]))]
    (search (sub1 (vector-length a-vec)))))

;; OBSERVE how you can write the function so that position either
;; refers to the last index you need to look at or the first one
;; you don't need to look at.  Confusing these is a very common
;; mistake -- your code must be consistent!

;; In this case, the first version is preferable, since it allows
;; zero-length vectors.  The second version can be modified to
;; work with zero-length vectors, e.g., by changing the base case to
;;   [(= -1 position)  false]
;; That would result in essentially the first version, except that
;; the meaning of "position" would differ by 1.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (vec-search-up1? pred? a-vec)
  (local [;; search : natnum -> boolean
	  ;; Purpose: Returns whether any element
	  ;;          position..(vector-length a-vec)-1
	  ;;          of a-vec meets predicate pred?.
	  (define (search position)
	    (cond
	      [(= (vector-length a-vec) position)
	       false]
	      [else
		(or (pred? (vector-ref a-vec position))
		    (search (add1 position)))]))]
    (search 0)))

(define (vec-search-up2? pred? a-vec)
  (local [;; search : natnum -> boolean
	  ;; Purpose: Returns whether any element
	  ;;          (vector-length a-vec)-position..(vector-length a-vec)-1
	  ;;          of a-vec meets predicate pred?.
	  (define (search position)
	    (cond
	      [(zero? position)
	       false]
	      [else
		(or (pred? (vector-ref a-vec (- (vector-length a-vec)
						position)))
		    (search (sub1 position)))]))]
    (search (vector-length a-vec))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (vec-search-binary? n a-vec)
  (local [;; search : natnum natnum -> boolean
	  ;; Purpose: Return whether n is any element lo..hi-1 of a-vec.
	  (define (search lo hi)
	    (local [(define mid (truncate (/ (+ lo hi) 2)))]
	      (cond
		[(= lo hi)
		 false]
		[(= n (vector-ref a-vec mid))
		 true]
		[(< n (vector-ref a-vec mid))
		 (search lo (sub1 mid))]
		[(> n (vector-ref a-vec mid))
		 (search (add1 mid) hi)])))]
    (search 0 (vector-length a-vec))))

;; NOTE that this is just one way to write binary search.