Searching

• We have seen that membership in lists can be checked using the following:

if x in list:

• How does Python do this?
• Given a list of integers, how can you search through the values to find one you are looking for?

Linear Search

• Going through a list item by item to find the value you are looking for is called linear search.
• How would you program this in Python?

# linearSearch() searches for the item in myList and returns
# the index of item in the list myList, or -1 if not found.
# Inputs: item, the item to search for
#         myList, the list to search for item
# Output: the index where item was found or -1 if index was 
#         not in the list  
def linearSearch(item, myList):

    for index in range(len(myList)):
        if myList[index] == item:
            return index

    return -1

Analysis

• How can we analyze the efficiency of linear search?
• The easiest metric to use is the number of operations required to find the item you are looking for.
• An operation, for our purposes, is any arithmetic or boolean operation (i.e. checking for equality)
• To make things a little easier, we will only consider the number of operations required in the worst case.

Linear Search Analysis

• What is the worst case for linear search?

• When the item you are searching for is the last item in the list (or not in the list), all other items have to be searched before you find it. It is literally "the last place you looked."
• In this case it takes six operations to find the the item you are looking for in the worst case.

Analysis Metric

• Since the worst case is always when the item you are searching for is the last item in the list, the number of operations required in this case is equal to the length of the list.
• A better way to say this is given a list of length n, we require n operations to find an element in it, in the worst case.
• As n grows, the amount of work required grows linearly, so this is known as a linear time algorithm.

Improving Search

• If the list is sorted, there is a faster method to search for a specific value.
  That method of searching is called binary search.
• Think of how you would play the following game:
  • One player thinks of a number between 1 and 100.
  • The second player repeatedly guesses a number and the first player tells him/her whether the guess is too high, too low or correct.
• The best way to play this is to always guess halfway between the boundaries you know the answer to be in.
  • 50? Lower
  • 25? Lower
  • 12? Higher
  • 18? Higher
  • 21? Higher
  • 23? Lower
  • 22? Yes

Binary Search

• Now we can take this idea and translate it into a list searching problem.
• The key idea is to use two variables, called low and high, to keep track of the viable positions within the list where the sought after item can be found.

For example, suppose we were trying to find the word "strawberry".

• Let's go to the word that's right in the middle of the sorted list.
  low = 0, high = 7,
  mid = (7 + 0) / 2 => 3.
• "strawberry" comes after "cherry" in the dictionary, so we don't need to consider any words before "cherry" in the list.
  low = mid + 1 => 4, high = 7,
  mid = (4 + 7) / 2 => 5.
• "strawberry" comes after "mango", so we don't need to consider any words before it in the list.
  low = mid + 1 => 6, high = 7,
  mid = (6 + 7) / 2 => 6
• "strawberry" comes after "orange".
  low = mid + 1 => 7, high = 7,
  mid = (7 + 7) / 2 => 7
• "strawberry" comes after "pineapple".
  low = mid + 1 => 8, high = 7,
  as soon as low > high stop, not found

Another example, finding "banana".

• Start with the middle.
  low = 0, high = 7,
  mid = (0 + 7) / 2 => 3.
• "banana" comes before "cherry".
  low = 0, high = mid - 1 => 2,
  mid = (0 + 2) / 2 => 1
• "banana" comes after "avocado".
  low = mid + 1 => 2, high = 2,
  mid = (2 + 2) / 2 => 2
• "banana" is in the position we are looking at so we are done

Binary Search Code

• Seeing how binary search is done, how would you code it in Python?

# binarySearch() performs a binary search for an item in a list
# Inputs: list, the list to search
#         item, the item to search for
# Output: the index of item in the list, or -1 if not found
def binarySearch(list, item):

    low = 0
    high = len(list) - 1

    while low <= high:

        mid = (low + high) / 2


        # if found return the index
        if item == list[mid]:
            return mid

        # if item is in the 2nd half of the list
        elif item > list[mid]:
            low = mid + 1

        # if item is in the 1st half of the list
        else:
            high = mid - 1

    # item was not in list
    return -1

Analysis of Binary Search

• How much work does binarySearch do?

How fast is log₂(n) ?

How many accesses will it take to find X as we increase N ?

Keep in mind that a linear search of a list containing 1,000,000 items would require 1,000,000 accesses in the worst case.

So binary search which runs in log₂(n) is amazingly fast!

Command-line arguments

There are times when it would be convenient for your program to be able to get information from the operating system's command line. This allows programs to be run in batch mode where the output from one program can be the input for another, etc.

Any number of arguments can be passed from the command line into your program.

Here's an example of code that uses command-line arguments:

import sys

num = len(sys.argv)

for i in range(num):

    print "sys.argv[%d] = %s" % (i, sys.argv[i])

Here's the output:

linuxserver1.cs.umbc.edu[160] python commandLine.py 2 foo 7.5 bar snoopy jazz
sys.argv[0] = commandLine.py
sys.argv[1] = 2
sys.argv[2] = foo
sys.argv[3] = 7.5
sys.argv[4] = bar
sys.argv[5] = snoopy
sys.argv[6] = jazz
linuxserver1.cs.umbc.edu[161]

• In the sys module there is a list of strings known as argv. This list will consist of one or more strings.
• sys.argv[0] always contains the name of the executable
• As you see from the example above, each item entered on the command line after that becomes another item in the list of strings. These are known as command-line arguments.
• Everything entered on the command line is a string, so you'll need to cast items that are to be used as numbers.

Using command-line arguments

This example uses command line arguments to give the program the name of the input file to use and the name of the output file to write during processing. This is a very common use of command line arguments.

If your program needs command line arguments in order to run, then you should have a clearly marked usage instructions in your file header comment to explain how to run the program.

# commandLine.py
# Sue Evans
# 11/17/09
# All sections
# bogar@cs.umbc.edu
#
# This program illustrates using command-line arguments
# It also uses file-handling, strings, lists & dictionaries
#
# This program requires command line arguments which are the
# filename of the input file and the filename of the output
# file, in that order.

import sys
import string

NUM_ARGS = 3
ANSWER_KEY = ['T','T','F','a','b','c']
ANSWER1_POS = 2
OFFSET = 4

def main():

    # make sure there are NUM_ARGS arguments on the command line
    # exit if not
    if len(sys.argv) != NUM_ARGS:
        print "This program requires command line arguments."
        print "The first argument is the filename of the input file."
        print "The second argument is the filename of the output file."    
        sys.exit()

    grades = {}

    # open file for input
    infile = open(sys.argv[1], "r")

    # for each student read in a line, strip it and
    # split it into the student's name and a string of his answers
    for line in infile:
        student = string.strip(line)
        student = string.split(student)
        size = len(student[1])

        # change the string of answers to a list of answers
        answers = []
        for i in range(ANSWER1_POS, size, OFFSET):
            answers.append(student[1][i])

        # make the student's name the key and his list of answers the value
        grades[student[0]] = answers

        # calculate the student's score
        score = 0
        size = len(answers)
        for question in range(size):
            if answers[question] == ANSWER_KEY[question]:
                score += 1

        # change the value to be just the score instead of a
        # list of answers
        grades[student[0]] = score

    # close the infile and open the outfile
    infile.close()
    outfile = open(sys.argv[2], "w")

    # make a list of the keys and sort them
    names = grades.keys()
    names.sort()

    # write the sorted student's names and their scores to the outfile
    for name in names:
        outfile.write(name + "\t" + str(grades[name]) + "\n")

    # close the output file
    outfile.close()


main()

Here's the input file, answers.txt :

Barnes,Beth ['T','T','F','a','b','c']
Carson,Ed ['T','F','T','a','b','b']

Let's run it!

linuxserver1.cs.umbc.edu[205] python commandLine.py answers.txt grades.out
linuxserver1.cs.umbc.edu[206]

Here's grades.out :

Barnes,Beth     6
Carson,Ed       3

Since I chose to use a dictionary, things became out of order immediately. Therefore, getting a list of keys and sorting them was necessary to get the roster back into sorted order by the students' last names.

Command-line argument Exercise

Write a program that will add values passed in as command-line arguments and will print their sum. The user may enter as many values as they choose on the command line.