Lecture 3/30/2020
Agenda:
-
Search
-
Linear Search
-
Analysis of Algorithms (Intro)
Whiteboard Notes:
-
-
Errata: the average runtime of algorithm #1 is (N+1)/2, not N/2
-
Notes has been cleaned up slightly for clarity
-
linearsearch-bool.py
Algorithm #1
def search(x, L):
"""
Search the list L for the element x
param L: a list of any ordered type
param x: an element to find (or same type as elements in L)
Returns True if the item is found; False otherwise
"""
for i in range(len(L)):
val = L[i]
if val == x:
return True
return False
def main():
numbers = [23, 77, -34, 45, 99, -4]
found = search(80, numbers)
if found:
print("Found!")
else:
print("Not found!")
main()
Algorithm #2
def search(x, L):
"""
Search the list L for the element x
param L: a list of any ordered type
param x: an element to find (or same type as elements in L)
Returns True if the item is found; False otherwise
"""
found = False
for i in range(len(L)):
val = L[i]
if val == x:
found = True
return found
def main():
numbers = [23, 77, -34, 45, 99, -4]
found = search(80, numbers)
if found:
print("Found!")
else:
print("Not found!")
main()
Using Python’s built-in search
def search(x, L):
"""
Search the list L for the element x
param L: a list of any ordered type
param x: an element to find (or same type as elements in L)
Returns True if the item is found; False otherwise
"""
found = val in L # Python's built-in search
return found
def main():
numbers = [23, 77, -34, 45, 99, -4]
found = search(80, numbers)
if found:
print("Found!")
else:
print("Not found!")
main()
linearsearch-index.py
def search(x, L):
"""
Search for the value x in the list L
Param x: a value
Param L: a list with the same type as x
Returns (int): the index where x is located; -1 if not found
"""
for i in range(len(L)):
val = L[i]
if val == x:
return i
return -1
def main():
numbers = [23, 77, -34, 45, 99, -4]
val = 99
index = search(99, numbers)
if index != -1:
print("We found %d at location %d"%(val, index))
else:
print("We didn't find %d"%(val))
Lecture 4/1/2020
Lecture 4/3/2020
Agenda:
-
Binary search vs linear search
-
Rules of Big-Oh
-
Algorithm analysis practice
Whiteboard notes:
Handouts
Binary Search Practice:
Please see your inclass directory for the source code for wordsearch.py