Lecture 3/30/2020

Agenda:

  • Search

  • Linear Search

  • Analysis of Algorithms (Intro)

Whiteboard Notes:

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

Agenda

  • Binary search

Whiteboard

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