- Why am I teaching binary search.
- The Overview -- at each step, eliminate half of your data.  That goes to O(log n).
- Do For-Class.odp

- Talk about implementation and how it's typically harder than the concept.  
  Say you've got some advice aboutthat.

------------------------------------------------------------
Canonical example -- search in a sorted array.

txt/words.txt has 24,853 words, all lower case, sorted.
- Do wc, head, tail, sort.

- Write a program that reads words, and then does binary search.
  Start with src/dict_skeleton.cpp and write Create() and Search().
  Test it on txt/words-12.txt

  find attention, debtor, efficient and hogan
  find aaa, zzz and mmm, which are not there

- Find jjj in the big words file -- print out low, middle, high (code is in dict_bsearch).

- Compare with a set and an unordered set.

- Using start/size rather than high low.  Show the picture in jpg/start-size.jpg
  Use that picture to write the code.  (src/dict_bs_ss.cpp).

------------------------------------------------------------
Optimization problem

General form: f(v) = no for all v < v_opt, and yes for all v >= v_opt.  Find v_opt().  
              If test is O(n), then binary search is O(n log v).

Go over koko_eating_bananas - scripts/koko_exp.sh

Example 1: piles = [ 3, 6, 7, 11 ], h = 8 (answer is 4) -- show how 3 makes h too high.
Example 2: piles = [ 30, 11, 23, 4, 20 ], h = 5 (answer is 30)
Example 3: piles = [ 30, 11, 23, 4, 20 ], h = 6 (answer is 23)

Think about binary search -- k = 0.  k = 10^9.  If you increase k, you'll decrease the timesteps.
Think about binary search -- k = 0.  k = 10^9.  If you decrease k, you'll increase the timesteps.

Perfect.

Broad strokes of the binary search.  Now show the picture, and talk through why you want
to look at the largest element in the blue section rather than the smallest element in the
pink section.

Write the code -- start with koko_skeleton and then write the code.

------------------------------------------------------------
Second Optimization problem

Do scripts/max_min_exp.sh

Example 1: nums = [10, 1, 2, 7, 1, 3 ] p = 2.  Ans = 2.

Formulate the problem as a binary search:

f(v) is "yes" if you can find p distinct pairs whose differences are all less than or equal to v.
f(v) is "no" if you cannot find p distinct pairs whose differences are all less than or equal to v.

Definitely a v_opt.  Write the code -- start with srv/Min_The_Max_Skeleton.cpp, and then
add a method f(v).  Test it.  

Then do the binary search, using the picture again.