1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-advanced-reader.ss" "lang")((modname |29.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 ;binary-contains? : (vectorof number) [sorted] N -> N or false
5 Given avector (sorted) and key, determines the index of the key in the vector if it occurs using the binary-search algorithm. Otherwise, returns false.
7 (define (binary-contains? avector key)
14 Exercise 29.3.9. Develop the function binary-contains?. It consumes a sorted vector of numbers and a key, which is also a number. The goal is to determine the index of the key, if it occurs in the vector, or false. Use the binary-search algorithm from section 27.3.
16 Determine the abstract running time of binary-contains? and compare with that of contains?, the function that searches for a key in a vector in the linear fashion of vector-contains-doll?.
18 Suppose we are to represent a collection of numbers. The only interesting problem concerning the collection is to determine whether it contains some given number. Which data representation is preferable for the collection: lists or vectors? Why?