Exercise 4.4
Binary search in sorted vectors ***

Linear search, as illustrated by other exercises, is not efficient. It is often attractive to organize data in a sorted vector, and to do binary search in the vector.

This exercise is meant to illustrate a real-life higher-order function, generalized with several parameters that are functions themselves.

Program a function binary-search-in-vector, with the following signature:

  (binary-search-in-vector v el sel el-eq? el-leq?)

v is the sorted vector. el is the element to search for. If v-el is an element in the vector, the actual comparison is done between el and (sel v-el). Thus, the function sel is used as a selector on vector elements. Equality between elements is done by the el-eq? function. Thus, (el-eq? (sel x) (sel y)) makes sense on elements x and y in the vector. The ordering of elements in the vector is defined by the el-leq? function. (el-leq? (sel x) (sel y)) makes sense on elements x and y in the vector.

The call (binary-search-in-vector v el sel el-eq? el-leq?) searches the vector via binary search and it returns an element el-v from the vector which satisfies (el-eq? (sel el-v) el). If no such element can be located, it returns #f.

Here are some examples, with elements being cons pairs:

  (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 7 car = <=)    =>
  (7 . i)

  (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 2 car = <=)    =>
  (2 . x)

  (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 10 car = <=)   =>
  #f

Be sure to program a tail recursive solution.