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???