WEEK09: searching, analysis of algorithms
---------------------------------------------------------------
 M: linear and binary search

ANNOUNCEMENTS:
 - quiz 4 review (do problems on board)
 - Lab 7 due Tuesday night 

NOTE: we're mostly done with teaching you python at this point.
There's lots more you could learn about python, but you've got
the basics now, and enough to write some interesting programs.

From here on out we'll focus more on Computer Science, rather
than computer programming...

SEARCHING:

 - motivation...www.google.com (searching and sorting)

 - basic search question...is x in y? (where x is some single
   value, and y is a group of values)

 - for us, x is a simple variable, and y is a list

 - if x = 12, and y = [7,30,-29,-4,88,49,-29,100,92], is x in y??

 - you can actually use the "in" operator to answer this:

>>> x = 12
>>> y = [7,30,-29,-4,88,49,-29,100,92]
>>> x in y
False
>>> x = 88
>>> x in y
True

 - how does the "in" operator work?? how would you search through
   the list and see if a certain value is there or not??


LINEAR SEARCH: go one at a time, through the whole list (a for loop!)

 - play guessing game: I am thinking of a number from 1-100...
 - what is "worst case" number of guesses?
 - best case number of guesses?
 - how much worse would the worst case be if we make the guess 1-200?

YOUR TURN:

  - write a linearSearch(x,L) function, IN A FILE CALLED searches.py,
    that looks for x in L

  - for example, it might be called from a main() (also in searches.py)
    like this:

def main():
  L = [5,88,2,-6,109,74,52]
  x = 109
  print linearSearch(x,L)

  - your function should return the index of the first occurance of
    x in L, if x is found in L, and a -1 if x is NOT found in L

  - for example, the above main() would print 4


def linSearch(x, nums):
    for i in range(len(nums)):
        if nums[i] == x:       # item found, return the index value
            return i

    return -1                  # loop finished, item was not in list

 - is linSearch any good? how long does it take? does it 
   matter if len(nums) is 10 or 10,000,000,000???

 - in the best case, the item you're looking for is first in the
   list. In the worst case, the item is last or not in the list:

        best case: takes 1 "step"
        worst case: takes len(nums) "steps"

 - if we double the size of the list (nums), the worst case also
   doubles in size. This means the time it takes linSearch to work
   is proportional to the size of the list (if you plot this out
   (num steps vs size of data), it's a STRAIGHT LINE, so we call it 
   LINEAR search)

 - add this __name__ stuff to the bottom of your searches.py file:

def linearSearch(x, L):
  """comment"""
  # function code here

def main():
  L = [5,88,2,-6,109,74,52]
  x = 109
  print linearSearch(x,L)

if __name__ == "__main__": main()

 - after you save and quit that searches.py file, try this (in
   the same dir as searches.py):

$ python
>>> from searches import linearSearch
>>> help(linearSearch)
Help on function linearSearch in module searches:

linearSearch(x, L)
    Use linear search to find x in L. If found, return
    first index of x in L. If not found, return -1

>>> linearSearch(5, [0,1,2,3,4,5])
5
>>> linearSearch(77, [0,1,2,3,4,5])
-1
>>> linearSearch("pony", [0,1,2,3,4,5])
-1
>>> linearSearch("pony", ["unicorn","donkey","horse","pony","zebra"])
3



BINARY SEARCH:

 - *if* the list is sorted, there's a better way!
 - play guessing game again: I am thinking of a number from 1-100...
   but this time give info (too low or too high) with each
   incorrect guess
 - what is the worst-case number of guesses??? and how is that
   related to the size of the data???