CS211 Spring 2002
Lecture 14: Searching
3/6/2003
-------------------------------------------------------------------------------
0) Announcements
   + Prelim 1 (T1) tonight (see website for rooms) (bring ID)
   + A4 due 3/12 (see online material)

   Overview:
   + more about big oh (oh no!)
   + searching:
     - linear
     - binary
   + intro to sorting
     - insert
     - selection
   + analysis of searching/sorting
-------------------------------------------------------------------------------
1) Searching and Sorting and Data Structures

   Programing (and OOP):



   Data structures:



   Providing of information:



   Searching



   Sorting



   Comparable interface




-------------------------------------------------------------------------------
2) Chaotic Search















-------------------------------------------------------------------------------
3) Linear Search

   Standard search:



   Linear:




 
   Somewhat generic code (could be better...how?):

      public static boolean linearSearch(Comparable[] c, Object key) {
         int i=0;
         while(i < c.length)
            if (c[i].compareTo(key)==0) return true;
            else i++;
         return false;
      }

   Asymptotic complexity:







   Other scenarios?


   Conclusion:




   Applications:
   + continuous data 


   + discrete:


-------------------------------------------------------------------------------
4) Binary Search

   Applications (continued):



   Number guessing:
     + strategies for guessing a number between 1 and 100









     + tallies for different size games:
         range    linear   binary  pattern of guesses
         1-1      1        1
         1-10     10       5       (5-10,7-10,8-10,9-10,10)
         1-100    100      8       (1-50,1-25,1-13,1-7,1-4,1-3,1-2,1)
         1-1000   1000     11      (500,250,125,63,32,16,8,4,3,2,1)
   
     + binary better!
     + why does it work here? numbers (the range) are sorted!

   General algorithm:





  
   Asymptotic complexity?
     + for given size n, what's worst case?
     + count comparisons of m==key (active operation)
     + approximate analysis:

       n   comps  pattern of search (assume last elem is the one we want)
                  (o=not inspected,x=inspected)
                  o->x
                  oo->xo->xx
                  oooo->oxoo->oxxo->oxxx
                  oooooooo->oooxoooo->oooxoxoo->oooxoxxo->oooxoxxx
                  oooooooxoooooooo->see pattern for 8

       (other values of n? need to ceiling operation... we're trying to
        find a pattern of worst cases first!)
       












   
   What about unsorted collection?
 
       ex) {1, 4, 3, 5, 2}
            - look for the 2 with binary search
            - pattern: 3, 4, 1 because 4 is less than 5
            - crap! it doesn't work
            - need sorting....
 
   What about continuous data? (like equns) 
     + already sorted! no problem

   Recursive binary search (alternative code):     
     + see pg 460 DS&A

   Handy way to sort:
     + http://java.sun.com/j2se/1.4/docs/api/java/util/Arrays.html
-------------------------------------------------------------------------------