"Big O" Notation
----------------------
 Need to measure the amount of work required by
   an algorithm relative to the size of the input

 Gives us a means to compare algorithms that do
   the same thing -- i.e. which one is better?


 EXAMPLE PROBLEM:
 -- Search a list (array) for a given element

 --> Solution: start at the first element
               compare
               if found, great -- we're done
               if not found, go to second element
                                   etc.

              LINEAR SEARCH


  List (array) is size n

  BEST CASE: find it in the first comparison
             Constant Time   O(1)

  WORST CASE: find it in the last comparison
                OR we don't find it at all
             Linear Time     O(n)

  AVERAGE CASE: find it somewhere in the middle
             Linear Time   O(n/2) ==> O(n)


   for ( int i = 0 ; i < n ; i++ )
   {
      if ( element == arr[i] )
      {
         found = true;
      }
   }

-------------------------------------------------

 ASSUMPTION: the list is in sorted order

 Binary search: list is size n = 9
                midpoint index is 9/2 = 4

                we're looking for 80

     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: |  9 | 12 | 18 | 27 | 36 | 40 | 80 | 90 | 98 |
    ----------------------------------------------
                           ^

                  compare 36 with 80


     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: |  9 | 12 | 18 | 27 | 36 | 40 | 80 | 90 | 98 |
    ----------------------------------------------
                             |==>   ^         <==|


                   midpoint is 4/2 = 2

                  compare 80 with 80 -- FOUND
  


e.g.
     BINARY SEARCH FOR 40

     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: |  9 | 12 | 18 | 27 | 36 | 40 | 80 | 90 | 98 |
    ----------------------------------------------
                           ^

                 right-endpoint is [8]
                 left-endpoint is [0]
                 midpoint is (8-0)/2 = [4]
                 compare 36 with 40


     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: | XX | XX | XX | XX | XX | 40 | 80 | 90 | 98 |
    ----------------------------------------------
                                     ^
             right-endpoint is [8]
             left-endpoint is last-midpoint + 1
                           is [5]
         midpoint is left-endpoint + (8-5)/2
                       = [5] + 3/2 = [6]
                  compare 80 with 40
     

     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: | XX | XX | XX | XX | XX | 40 | XX | XX | XX |
    ----------------------------------------------

            right-endpoint is last-midpoint - 1
                           is [5]
            left-endpoint is still [5]
         
       STOP when left-endpoint == right-endpoint

            recursion stops -- we found 40
                           or we didn't find it...


     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: | XX | XX | XX | XX | XX | 42 | XX | XX | XX |
    ----------------------------------------------





e.g.
     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: | 10 | 11 | 15 | 21 | 33 | 42 | 57 | 87 | 91 |
    ----------------------------------------------

     BINARY SEARCH FOR 21:
       left-endpoint, right-endpoint, midpoint,
         and comparison



--------------------------------------------------


e.g.
     [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
    ----------------------------------------------
 a: | 11 | 13 | 15 | 33 | 21 | 42 | 57 | 91 | 87 |
    ----------------------------------------------

  bubble sort:
  (1) find the smallest element
       and swap into index [0]
  (2) find the next-smallest element
       and swap into index [1]







 // len is the number of names in the array

 bool binary_search( string names[], int len,
                     int left_endpoint,
                     int right_endpoint )