CS 3341, Recitation Section, Problem list 6.  For Feb 24, 26.

Work on Problem 6 of Section 4.3 (page 137):

   How can we use binary search for range searching, i.e.,
   for finding all the elements in a sorted array A whose values
   fall between two given values L and U (inclusively), L <= U?
   What is the worst-case efficiency of this algorithm?

Hints: In case L and U are elements of A, this is easy, so the
main problem is the case in which L or U are not elements of A.
How would you modify the algorithm for binary search on page 134?
(You should check how the algorithm terminates in case of an
unsuccessful search.  Be careful not to confuse the variables
l and r in the algorithm, which are indexes into the array,
with the values L and U, which are the same type as the elements
of A, and which fall in order somewhere along with the elements of A.)

For example, suppose A holds the strings:

String[] A = {"Apr","Aug","Dec","Feb","Jan","Jul",
              "Jun","Mar","May","Nov","Oct","Sep"};
              
First consider a range like L = "Dec", U = "May".
Then consider a range like L = "Dog", U = "Nut".
(Here L and U are strings, just like the elements of A,
while the variables l and r are integers, indexes in A.)