Chapter 15: Searching

Searching is an important and very common operation that computers do all the time. Searches are used every time someone does a ctrl-f for “find”, when a user uses “type-to” to quickly select an item, or when a web server pulls information about a customer to present a customized web page with the customer's order.

There are a lot of ways to search for data. Google has based an entire multi-billion dollar company on this fact. This chapter introduces the two simplest methods for searching, the linear search and the binary search.

15.1 Reading From a File

Before discussing how to search we need to learn how to read data from a file. Reading in a data set from a file is way more fun than typing it in by hand each time.

Let's say we need to create a program that will allow us to quickly find the name of a super-villain. To start with, our program needs a database of super-villains. To download this data set, download and save this file:
http://ProgramArcadeGames.com/chapters/16_searching/super_villains.txt
These are random names generated by the nine.frenchboys.net website, although last I checked they no longer have a super-villain generator.

Save this file and remember which directory you saved it to.

In the same directory as super_villains.txt, create, save, and run the following python program:

file = open("super_villains.txt")

for line in file:
    print(line)

There is only one new command in this code open. Because it is a built-in function like print, there is no need for an import. Full details on this function can be found in the Python documentation but at this point the documentation for that command is so technical it might not even be worth looking at.

The above program has two problems with it, but it provides a simple example of reading in a file. Line 1 opens a file and gets it ready to be read. The name of the file is in between the quotes. The new variable file is an object that represents the file being read. Line 3 shows how a normal for loop may be used to read through a file line by line. Think of file as a list of lines, and the new variable line will be set to each of those lines as the program runs through the loop.

Try running the program. One of the problems with the it is that the text is printed double-spaced. The reason for this is that each line pulled out of the file and stored in the variable line includes the carriage return as part of the string. Remember the carriage return and line feed introduced back in Chapter 1? The print statement adds yet another carriage return and the result is double-spaced output.

The second problem is that the file is opened, but not closed. This problem isn't as obvious as the double-spacing issue, but it is important. The Windows operating system can only open so many files at once. A file can normally only be opened by one program at a time. Leaving a file open will limit what other programs can do with the file and take up system resources. It is necessary to close the file to let Windows know the program is no longer working with that file. In this case it is not too important because once any program is done running, the Windows will automatically close any files left open. But since it is a bad habit to program like that, let's update the code:

file = open("super_villains.txt")

for line in file:
    line = line.strip()
    print(line)

file.close()

The listing above works better. It has two new additions. On line 4 is a call to the strip method built into every String class. This function returns a new string without the trailing spaces and carriage returns of the original string. The method does not alter the original string but instead creates a new one. This line of code would not work:

line.strip()

If the programmer wants the original variable to reference the new string, she must assign it to the new returned string as shown on line 4.

The second addition is on line 7. This closes the file so that the operating system doesn't have to go around later and clean up open files after the program ends.

15.2 Reading Into an Array

It is useful to read in the contents of a file to an array so that the program can do processing on it later. This can easily be done in python with the following code:

# Read in a file from disk and put it in an array.
file = open("super_villains.txt")

name_list = []
for line in file:
    line = line.strip()
    name_list.append(line)

file.close()

This combines the new pattern of how to read a file, along with the previously learned pattern of how to create an empty array and append to it as new data comes in, which was shown back in Chapter 7. To verify the file was read into the array correctly a programmer could print the length of the array:

print( "There were",len(name_list),"names in the file.")

Or the programmer could bring the entire contents of the array:

for name in name_list:
    print(name)

Go ahead and make sure you can read in the file before continuing on to the different searches.

15.3 Linear Search

If a program has a set of data in an array, how can it go about finding where a specific element is? This can be done one of two ways. The first method is to use a linear search. This starts at the first element, and keeps comparing elements until it finds the desired element (or runs out of elements.)

15.3.1 Linear Search Algorithm

# --- Linear search
key = "Morgiana the Shrew"

i = 0
while i < len(name_list) and name_list[i] != key:
    i += 1

if i < len(name_list):
    print( "The name is at position", i)
else:
    print( "The name was not in the list." )

The linear search is rather simple. Line 4 sets up an increment variable that will keep track of exactly where in the list the program needs to check next. The first element that needs to be checked is zero, so i is set to zero.

The next line is a bit more complex. The computer needs to keep looping until one of two things happens. It finds the element, or it runs out of elements. The first comparison sees if the current element we are checking is less than the length of the list. If so, we can keep looping. The second comparison sees if the current element in the name list is equal to the name we are searching for.

This check to see if the program has run out of elements must occur first. Otherwise the program will check against a non-existent element which will cause an error.

Line 6 simply moves to the next element if the conditions to keep searching are met in line 5.

At the end of the loop, the program checks to see if the end of the list was reached on line 8. Remember, a list of n elements is numbered 0 to n-1. Therefore if i is equal to the length of the list, the end has been reached. If it is less, we found the element.

15.4 Variations On The Linear Search

Variations on the linear search can be used to create several common algorithms. For example, say we had a list of aliens. We might want to check this group of aliens to see if one of the aliens is green. Or are all the aliens green? Which aliens are green?

To begin with, we'd need to define our alien:

class Alien:
    """ Class that defines an alien"""
    def __init__(self, color, weight):
        """ Constructor. Set name and color"""
        self.color = color
        self.weight = weight

Then we'd need to create a function to check and see if it has the property that we are looking for. In this case, is it green? We'll assume the color is a text string, and we'll convert it to upper case to eliminate case-sensitivity.

def has_property(my_alien):
    """ Check to see if an item has a property.
    In this case, is the alien green? """
    if my_alien.color.upper() == "GREEN":
        return True
    else:
        return False

15.4.1 Does At Least One Item Have a Property?

Is at least one alien green? We can check. The basic algorithm behind this check:

def check_if_one_item_has_property_v1(my_list):
    """ Return true if at least one item has a
    property. """
    i = 0
    while i < len(my_list) and not has_property(my_list[i]):
        i += 1

    if i < len(my_list):
        # Found an item with the property
        return True
    else:
        # There is no item with the property
        return False

This could also be done with a for loop. In this case, the loop will exit early by using a return once the item has been found. The code is shorter, but not every programmer would prefer it. Some programmers feel that loops should not be prematurely ended with a return or break statement. It all goes to personal preference, or the personal preference of the person that is footing the bill.

def check_if_one_item_has_property_v2(my_list):
    """ Return true if at least one item has a
    property. Works the same as v1, but less code. """
    for item in my_list:
        if has_property(item):
            return True
    return False

15.4.2 Do All Items Have a Property?

Are all aliens green? This code is very similar to the prior example. Spot the difference and see if you can figure out the reason behind the change.

def check_if_all_items_have_property(my_list):
    """ Return true if at ALL items have a property. """
    for item in my_list:
        if not has_property(item):
            return False
    return True

15.4.3 Create a List With All Items Matching a Property

What if you wanted a list of aliens that are green? This is a combination of our prior code, and the code to append items to a list that we learned about back in Chapter 7.

def get_matching_items(list):
    """ Build a brand new list that holds all the items
    that match our property. """
    matching_list = []
    for item in list:
        if has_property(item):
            matching_list.append(item)
    return matching_list

How would you run all these in a test? The code above can be combined with this code to run:

alien_list = []
alien_list.append(Alien("Green", 42))
alien_list.append(Alien("Red", 40))
alien_list.append(Alien("Blue", 41))
alien_list.append(Alien("Purple", 40))

result = check_if_one_item_has_property_v1(alien_list)
print("Result of test check_if_one_item_has_property_v1:", result)

result = check_if_one_item_has_property_v2(alien_list)
print("Result of test check_if_one_item_has_property_v2:", result)

result = check_if_all_items_have_property(alien_list)
print("Result of test check_if_all_items_have_property:", result)

result = get_matching_items(alien_list)
print("Number of items returned from test get_matching_items:", len(result))

For a full working example see:
programarcadegames.com/python_examples/show_file.php?file=property_check_examples.py

These common algorithms can be used as part of a solution to a larger problem, such as find all the addresses in a list of customers that aren't valid.

15.5 Binary Search

A faster way to search a list is possible with the binary search. The process of a binary search can be described by using the classic number guessing game “guess a number between 1 and 100” as an example. To make it easier to understand the process, let's modify the game to be “guess a number between 1 and 128.” The number range is inclusive, meaning both 1 and 128 are possibilities.

If a person were to use the linear search as a method to guess the secret number, the game would be rather long and boring.

Guess a number 1 to 128: 1
Too low.
Guess a number 1 to 128: 2
Too low.
Guess a number 1 to 128: 3
Too low.
....
Guess a number 1 to 128: 93
Too low.
Guess a number 1 to 128: 94
Correct!

Most people will use a binary search to find the number. Here is an example of playing the game using a binary search:

Guess a number 1 to 128: 64
Too low.
Guess a number 1 to 128: 96
Too high.
Guess a number 1 to 128: 80
Too low.
Guess a number 1 to 128: 88
Too low.
Guess a number 1 to 128: 92
Too low.
Guess a number 1 to 128: 94
Correct!

Each time through the rounds of the number guessing game, the guesser is able to eliminate one half of the problem space by getting a “high” or “low” as a result of the guess.

In a binary search, it is necessary to track an upper and a lower bound of the list that the answer can be in. The computer or number-guessing human picks the midpoint of those elements. Revisiting the example:

A lower bound of 1, upper bound of 128, mid point of $\dfrac{1+128}{2} = 64.5$.

Guess a number 1 to 128: 64
Too low.

A lower bound of 65, upper bound of 128, mid point of $\dfrac{65+128}{2} = 96.5$.

Guess a number 1 to 128: 96
Too high.

A lower bound of 65, upper bound of 95, mid point of $\dfrac{65+95}{2} = 80$.

Guess a number 1 to 128: 80
Too low.

A lower bound of 81, upper bound of 95, mid point of $\dfrac{81+95}{2} = 88$.

Guess a number 1 to 128: 88
Too low.

A lower bound of 89, upper bound of 95, mid point of $\dfrac{89+95}{2} = 92$.

Guess a number 1 to 128: 92
Too low.

A lower bound of 93, upper bound of 95, mid point of $\dfrac{93+95}{2} = 94$.

Guess a number 1 to 128: 94
Correct!

A binary search requires significantly fewer guesses. Worst case, it can guess a number between 1 and 128 in 7 guesses. One more guess raises the limit to 256. 9 guesses can get a number between 1 and 512. With just 32 guesses, a person can get a number between 1 and 4.2 billion.

To figure out how large the list can be given a certain number of guesses, the formula works out like $n=x^{g}$ where $n$ is the size of the list and $g$ is the number of guesses. For example:
$2^7=128$ (7 guesses can handle 128 different numbers)
$2^8=256$
$2^9=512$
$2^{32}=4,294,967,296$

If you have the problem size, we can figure out the number of guesses using the log function. Specifically, log base 2. If you don't specify a base, most people will assume you mean the natural log with a base of $e \approx 2.71828$ which is not what we want. For example, using log base 2 to find how many guesses:
$log_2 128 = 7$
$log_2 65,536 = 16$

Enough math! Where is the code? The code to do a binary search is more complex than a linear search:

# --- Binary search
key = "Morgiana the Shrew"
lower_bound = 0
upper_bound = len(name_list)-1
found = False

# Loop until we find the item, or our upper/lower bounds meet
while lower_bound <= upper_bound and not found:

    # Find the middle position
    middle_pos = (lower_bound + upper_bound) // 2

    # Figure out if we:
    # move up the lower bound, or
    # move down the upper bound, or
    # we found what we are looking for
    if name_list[middle_pos] < key:
        lower_bound = middle_pos + 1
    elif name_list[middle_pos] > key:
        upper_bound = middle_pos - 1
    else:
        found = True

if found:
    print( "The name is at position", middle_pos)
else:
    print( "The name was not in the list." )

Since lists start at element zero, line 3 sets the lower bound to zero. Line 4 sets the upper bound to the length of the list minus one. So for a list of 100 elements the lower bound will be 0 and the upper bound 99.

The Boolean variable on line 5 will be used to let the while loop know that the element has been found.

Line 8 checks to see if the element has been found or if we've run out of elements. If we've run out of elements the lower bound will end up equaling the upper bound.

Line 11 finds the middle position. It is possible to get a middle position of something like 64.5. It isn't possible to look up position 64.5. (Although J.K. Rowling was rather clever in enough coming up with Platform $9\frac{3}{4}$, that doesn't work here.) The best way of handling this is to use the // operator first introduced way back in Chapter 5. This is similar to the / operator, but will only return integer results. For example, 11 // 2 would give 5 as an answer, rather than 5.5.

Starting at line 17 the program checks to see if the guess is high, low, or correct. If the guess is low, the lower bound is moved up to just past the guess. If the guess is too high, the upper bound is moved just below the guess. If the answer has been found, found is set to True ending the search.

With the a list of 100 elements, a person can reasonably guess that on average with the linear search, a program will have to check 50 of them before finding the element. With the binary search, on average you'll still need to do about seven guesses. In an advanced algorithms course you can find the exact formula. For this course, just assume average and worst cases are the same.

15.6 Review

15.6.1 Multiple Choice Quiz

Click here for a multiple-choice quiz.

15.6.2 Short Answer Worksheet

Click here for the chapter worksheet.

15.6.3 Lab

Click here for the chapter lab.

You are not logged in. Log in here and track your progress.