27. 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.

../../_images/search.png

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.

27.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:

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. They have other cool random name generators though.

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:

Read in a file
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Loop through each line in the file like a list
    for line in my_file:
        print(line)


main()

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 6 opens a file and gets it ready to be read. The name of the file is in between the quotes. The new variable my_file is an object that represents the file being read. Line 9 shows how a normal for loop may be used to read through a file line by line. Think of the 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:

Read in a file
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()
        print(line)

    my_file.close()


main()

The listing above works better. It has two new additions. On line 11 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 11.

The second addition is on line 14. 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.

27.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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Create an empty list to store our names
    name_list = []

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()

        # Add the name to the list
        name_list.append(line)

    my_file.close()

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


main()

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 Adding to a List. 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 print 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.

27.4. Linear Search Algorithm

Linear search
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# --- Linear search
key = "Morgiana the Shrew"

# Start at the beginning of the list
current_list_position = 0

# Loop until you reach the end of the list, or the value at the
# current position is equal to the key
while current_list_position < len(name_list) and name_list[current_list_position] != key:

    # Advance to the next item in the list
    current_list_position += 1

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

The linear search is rather simple. Line 5 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 current_list_position 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 12 simply moves to the next element if the conditions to keep searching are met in line 9.

At the end of the loop, the program checks to see if the end of the list was reached on line 14. 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.

The full example with both the reading in the file and the search is below:

Linear search
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Create an empty list to store our names
    name_list = []

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()

        # Add the name to the list
        name_list.append(line)

    my_file.close()

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

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

    # Start at the beginning of the list
    current_list_position = 0

    # Loop until you reach the end of the list, or the value at the
    # current position is equal to the key
    while current_list_position < len(name_list) and name_list[current_list_position] != key:
        # Advance to the next item in the list
        current_list_position += 1

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


main()

We can improve on this example by moving both the reading of the file and the search into their own functions:

Linear search
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def read_in_file(file_name):
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open(file_name)

    # Create an empty list to store our names
    name_list = []

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()

        # Add the name to the list
        name_list.append(line)

    my_file.close()

    return name_list


def linear_search(key, name_list):
    """ Linear search """

    # Start at the beginning of the list
    current_list_position = 0

    # Loop until you reach the end of the list, or the value at the
    # current position is equal to the key
    while current_list_position < len(name_list) and name_list[current_list_position] != key:

        # Advance to the next item in the list
        current_list_position += 1

    return current_list_position


def main():

    key = "Morgiana the Shrew"
    name_list = read_in_file("super_villains.txt")
    list_position = linear_search(key, name_list)

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


main()

27.6. Variations On The Linear Search With Objects

For example, say we had a list of objects for our text adventure. We might want to check that list and see if any of the items are in the same room as our player. Or if all the items are. Or we might want to build a list of items that the user is carrying if they are all in a “special” room that represents the player’s inventory.

To begin with, we’d need to define our adventure object:

Adventure Object class
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class AdventureObject:
    """ Class that defines an object in a text adventure game """

    def __init__(self, description, room):
        """ Constructor."""

        # Description of the object
        self.description = description

        # The number of the room that the object is in
        self.room = room

27.6.1. Does At Least One Item Have a Property?

Is at least one object in the specified room? We can check.

Check if list has an item that has a property - while loop
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def check_if_one_item_is_in_room_v1(my_list, room):
    """
    Return true if at least one item has a
    property.
    """
    i = 0
    while i < len(my_list) and my_list[i].room != room:
        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.

Check if list has an item that has a property - for loop
1
2
3
4
5
6
7
8
9
def check_if_one_item_is_in_room_v2(my_list, room):
    """
    Return true if at least one item has a
    property. Works the same as v1, but less code.
    """
    for item in my_list:
        if item.room == room:
            return True
    return False

27.6.2. Do All Items Have a Property?

Are all the adventure objects in the same room? This code is very similar to the prior example. Spot the difference and see if you can figure out the reason behind the change.

Check if all items have a property
1
2
3
4
5
6
7
8
def check_if_all_items_are_in_room(my_list, room):
    """
    Return true if at ALL items have a property.
    """
    for item in my_list:
        if item.room != room:
            return False
    return True

27.6.3. Create a List With All Items Matching a Property

What if you wanted a list of objects that are in room 5? This is a combination of our prior code, and the code to append items to a list that we learned about back in Introduction to Lists.

Create another list with all items matching a property
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def get_items_in_room(my_list, room):
    """
    Build a brand new list that holds all the items
    that match our property.
    """
    matching_list = []
    for item in my_list:
        if item.room == room:
            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:

Run Sample Functions
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def main():
    object_list = []
    object_list.append(AdventureObject("Key", 5))
    object_list.append(AdventureObject("Bear", 5))
    object_list.append(AdventureObject("Food", 8))
    object_list.append(AdventureObject("Sword", 2))
    object_list.append(AdventureObject("Wand", 10))

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

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

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

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


main()

For a full working example:

linear_search_variations.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class AdventureObject:
    """ Class that defines an alien"""

    def __init__(self, description, room):
        """ Constructor. Set name and color"""
        self.description = description
        self.room = room


def check_if_one_item_is_in_room_v1(my_list, room):
    """
    Return true if at least one item has a
    property.
    """
    i = 0
    while i < len(my_list) and my_list[i].room != room:
        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


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


def check_if_all_items_are_in_room(my_list, room):
    """
    Return true if at ALL items have a property.
    """
    for item in my_list:
        if item.room != room:
            return False
    return True


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


def main():
    object_list = []
    object_list.append(AdventureObject("Key", 5))
    object_list.append(AdventureObject("Bear", 5))
    object_list.append(AdventureObject("Food", 8))
    object_list.append(AdventureObject("Sword", 2))
    object_list.append(AdventureObject("Wand", 10))

    result = check_if_one_item_is_in_room_v1(object_list, 5)
    print("Result of test check_if_one_item_is_in_room_v1:", result)

    result = check_if_one_item_is_in_room_v2(object_list, 5)
    print("Result of test check_if_one_item_is_in_room_v2:", result)

    result = check_if_all_items_are_in_room(object_list, 5)
    print("Result of test check_if_all_items_are_in_room:", result)

    result = get_items_in_room(object_list, 5)
    print("Number of items returned from test get_items_in_room:", len(result))


main()

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.