Binary Search—Python

Binary searches work by splitting a collection in half and only searching on half of the collection while discarding the other half. This algorithm requires the collection to be sorted first.

Here’s the code

def binary_search(search_list, data):
    low = 0
    high = len(search_list) - 1

    while low <= high:
        mid = int(low + (high - low) / 2)

        if search_list[mid] == data:
            # Return the index because we
            # found our item
            return mid

        elif search_list[mid] < data:
            # Continue search at the top
            # half of search list
            low = mid + 1
        else:
            # Continue search at the
            # bottom of search list
            high = mid - 1

    # The item wasn't found
    return None


if __name__ == '__main__':
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    print('Sorting names...')
    names.sort()

    linda_index = binary_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

    teddy_index = binary_search(names, 'Teddy')
    if teddy_index:
        print('Teddy was found at ', str(teddy_index))
    else:
        print('Teddy was not found')

When run, we will get the following output.

Sorting names...
Linda Belcher found at  2
Teddy was not found

Ordered Linear Search—Python

Ordered Linear Searche’s are a varient of Unordered Linear Search. The main difference is that this algorithm expects the search list to be sorted prior to searching. For this reason, the Ordered Linear Search can be a little more efficient than it’s Unordered varient.

Here’s the code

from random import shuffle


def ordered_linear_search(search_list, data):
    for i in range(len(search_list) - 1):
        if search_list[i] == data:
            # Return the index of the item
            return i
        elif search_list[i] > data:
            # The idea here is to fail at this
            # point because search_list isn't sorted
            return None
    # We didn't find our item, so return None
    return None


if __name__ == '__main__':
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    print('Shuffling names')
    shuffle(names)

    linda_index = ordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

    teddy_index = ordered_linear_search(names, 'Teddy')
    if teddy_index:
        print('Teddy was found at ', str(teddy_index))
    else:
        print('Teddy was not found')

    print('Now sorting...')
    names.sort()

    linda_index = ordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

When run, you will notice that first we do not find the name ‘Linda Belcher’ because the list is shuffled. After sorting, the search will identifiy ‘Linda Belcher’ at index 2.

Shuffling names
Linda Belcher was not found
Teddy was not found
Now sorting...
Linda Belcher found at  2

Random Int—Python

There are many applications in programming where we have to randomly pick an element in a list. Python has the random module which includes a randint function for this exact purpose. Here’s an example.

from random import randint

if __name__ == '__main__':
    names = ['Bob Belcher',
             'Linda Belcher',
             'Gene Belcher',
             'Tina Belcher',
             'Lousie Belcher']
    num = randint(0, len(names) - 1) # -1 because lists are 0 based
    print('Random number was', num)
    print('Name picked randomly is', names[num])

When run, this code produces the following output (which is different each time the script is ran).

Random number was 4
Name picked randomly is Lousie Belcher

Continue—Python

The continue statement is used in Python to return program execution to the beginning of a loop. For a review of loops see for loops and while loops.

Let’s begin with a code example

names = ['Bob Belcher',
         'Linda Belcher',
         None,
         'Louise Belcher',
         'Tina Belcher',
         None,
         'Gene Belcher']

bob = ''
for name in names:
    if name is None:
        continue    # Go back to the top of the loop since
                    # since we can't do comparisons on None
    if 'Bob' in name:
        bob = name

In this situation, we have a list object that has a combination of Strings and Python’s None object. What we are doing is trying to find ‘Bob’ but to do that, we need a way to skip over the None objects or our program will crash. Lines 11 and 12 in the above code snippet do the job of checking if the elemnt name is None first. If it turns out that the element is None, line 12 uses the continue statement to return the execution to the top of the loop.

The continue keyword is useful when we process a loop of mixed types. Let’s take another example of where the keyword is also useful.

while True:
    fileName = input('Enter a file name => ')
    try:
        lines = open(fileName, 'r').readlines()
    except FileNotFoundError:
        print('Try a different file')
        continue # We can't do the next part because
                 # couldn't open the file
    for line in lines:
        print(line)

This code snippet asks the user for a file and then attempts to open the file for processing. However, if for some reason we can’t open the file, the program won’t be able to process lines 9 and 10. For this reason, we use the continue keyword to return program execution to the top of the loop and give the user an opportunity to open a different file.

Pass—Python

Python has a special pass keyword to do nothing. Here’s a code example

countdown = 15
while countdown > 0:
    if countdown > 10:
        pass # Don't do anything yet
    else:
        print('T - ', str(countdown))
    countdown -= 1
else:
    print ('We have liftoff!')

This code simulates a countdown, but we don’t actually want to print anything to the console until we get to 10. In this case, we set up an if condition that checks if countdown is greater than 10. If countdown is greater than 10, we use pass to do nothing.

In the real world, I tend to use pass when I am developing. Here is an example

def onNew():
    #TODO: Handle new file here
    pass

def onSave():
    #TODO: Handle saving a file here
    pass

def onOpen():
    #TODO: Handle opening a file here
    pass

def onError():
    #TODO: Handle user input errors here
    pass

repeat = True
while repeat:
    print('1) New...')
    print('2) Open...')
    print('3) Save...')
    print('4) Quit...')

    choice = input('Enter an option => ')
    if choice == 1:
        onNew()
    elif choice == 2:
        onOpen()
    elif choice == 3:
        onSave()
    elif choice == 4:
        repeat = False
    else:
        onError()

In this programming example, I’m in the process of developing a menu drive user interface. You can see the menu printed out in the while loop. The user is asked for a choice and then if/elif statements are used to respond to their choice. In each choice except 4, we are using function to handle the user’s choice. This keeps the user reponse code seperate from the user menu code (concept know as seperations of concerns).

Above the menu loop there are four functions: onNew(), onOpen(), onSave(), and onError(). Every single one of these functions has the pass keyword. Eventually the pass statements will get replaced with actual code to handle each event, but for now, I only want to test the menu code. Using pass in this fashion lets me run the program and make sure the menu is working properly before I continue developing the rest of the program.

Break Statement—Python

I’ve done a few posts now on loops. To review, Python has two kinds of loops: while loops and for loops.

I can think of plenty of times that we want to create an infinate loop. To review, an infintate loop is a loop that never ends. Consider this code.

while True:
    pass

Should you run this code, the program will never terminate because the loop condition is always True. In many cases, infinate loops are the result of programming errors, but let’s consider a menu driven program like this:

while True:
    print('1) New File')
    print('2) Open File')
    print('3) Save File')
    print('4) Exit...')

    choice = input('Enter choice => ')
    if choice == 1:
        pass # do something with a new file
    elif choice == 2:
        pass # do something to open a file
    elif choice == 3:
        pass # do something to save a file
    elif choice == 4:
        break # exit this loop and end the application

In this case, we want the program to program to continue to repeat this main menu until the user enters 4. That’s where the magic break keyword comes into play.

The break keyword liternally means to break out of a loop. This example is a common application of the loop but it doesn’t always have to be used in infinate loops. Let’s try and example with the for loop.

names = ['Bob Belcher',
         'Linda Belcher',
         'Louise Belcher',
         'Tina Belcher',
         'Gene Belcher']

bob = ''
for name in names:
    if 'Bob' in name:
        bob = name
        break   # There's no need to keep looping through
                # the rest of the list because we have found Bob

Nested Loops

In previous posts, we covered while and for loops. Python let’s us nest loops. Let’s start with an example.

grid = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [9, 8, 7, 6, 5, 4, 3, 2, 1],
]

for row in grid:
    for cell in row:
        print(str(cell))
    print('\n', end=' ')

When run, we get the following output

1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1

So why does this work? In our example, we have data structure that can be thought of in terms of an x,y grid. Basically, it’s a list that contains two lists: one list for each row.

When we begin our loop with for row in grid: we are starting a for loop with a variable named row. Everytime this loop updates, the row variable is assigned the next list object inside of the grid variable.

Now our next line of code is also a for loop: for cell in row. Remeber that row is a list object that corresponds to a row in the grid list. Each item inside of row is a number, so when this loop runs, the variable cell gets updated with a number inside of the list that is currently assigned to the row variable.

We can mix our loops also

grid = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [9, 8, 7, 6, 5, 4, 3, 2, 1],
]

for row in grid:
    index = 0
    while index < len(row):
        print(str(row[index]))
        index += 1

This code delivers the same output as the first example. The differnce is that this time, we have a while loop as our nested loop rather than a for loop. As you can see, this code is a little more complex than the first example, but the point of it was to demonstrate that it's possible to mix and match loops.

Also keep in mind that you can have loops that are infintely nested as long as your hardware can handle it. However, if you find that you are nesting loops deeper than two loops, then consider restructing your code since nesting loops that deep will impact the code's reability and make it difficult to debug.

While Loops—Python

Sometimes we need to repeat code in our programs for a certain number of executions. Let’s consider the classic triangle problem:

=
==
===
====
=====
======
=======
========
=========
==========

This is a typical problem that computer science students use to learn about loops. In this problem, we have to print a triangle to the console where the size is specified by the user. Since we don’t know the size of the triangle ahead of time, we won’t be able to do something like this:

print('=')
print('==')
print('===')
# continued...

Our issue is that right now, this code can only print a triangle that has a base size of three. If the user wants ten, we are out of luck. What we need is a programming construct that will continue to build the triangle until it hits the proper size.

Here is the example code of how to do this

size = int(input('Enter the size of the triangle => '))
counter = 0

while counter < size:  # counter < size is the terminating condition.
    # The next two lines repeat as long as condition < size
  print('=' * counter) # Print the triangle
  counter += 1 # Important! Update the counter variable! 

This code accomplishes what we want it to do. This is the output we get when we run this code.

Enter the size of the triangle => 5

=
==
===
====

Let’s talk about why this works. While loops begin with the while keyword followed by a condition. The loop will repeat code inside of the while block as long as the condition is true.

In our case, the condition is counter < size so as long as our counter is less than the size of the triangle that the user specified, our condition will be true and the loop will continue to repeat. As soon as size >= counter the loop will terminate and the program will return to it’s normal execution flow.

Inside of the triangle, we print our triangle and then update our counter variable by 1. It is critical that we update our counter variable because without it, the loop will run forever.

while counter < size:
    print('=' * counter)
print('Loop is over') # Note! We never get to this statement! How come?

The code above will run forever in what is called an 'infinate loop'. The reason this happens is that we fail to increment the counter variable. Remember that loops always run while the terminating condition is true. Since counter is always less than size, our condtion never becomes false and the loop runs forever.
Sometimes we make infinate loops on purpose

while True:
    print('Infinate loop')

Since we are passing the contant True to our loop here, our loop will run forever. It’s on the developer at this point to kill the loop, which will learn when we cover the break keyword.

Finally, Python let’s us add an else statement to while loops that will run once the loop is over.

size = int(input('Enter the size of the triangle => '))
counter = 0

while counter < size:
    print('=' * counter)
    counter += 1
else:
    print('triangle complete') # This code runs when the loop is over

For Loops—Python

Python has a for loop which is allows us to step through each element in an iterable (generally anything that defines __iter__ or __getitem__ such as files, lists, tuples, etc.).

First let’s go through an example of a for loop

for i in range(10):
    print(str(i))

When run, this code produces the following output

0
1
2
3
4
5
6
7
8
9

Let’s discuss how this works. Our loop begins with the keyword for followed by a variable or variables. After the variable, we have the in keyword followed by an iterable. The loop continues until there are no more items in the iterable.

In our example, the iterable is the range function. So when we have range(10) we are making a sequence of ten numbers 0-9. Everytime range produces a number, it gets assigned to the variable i. We then use print(str(i)) to print the value of i to the console.

Here is another demonstration of the for loop, this time using a list

names = ['Bob', 'Tina', 'Gene', 'Linda']

for name in names:
    print(name)

Lists implement the correct protocals that allow them to be used in for loops. In this case, we populate a list with some names. Everytime the loop executes, the name variable is updated with the next name in the list. We then print the name to the console.

The for loop let’s us have more than one variable in the loop.

names = [['Bob', 'Belcher'], 
        ['Tina', 'Belcher'], 
        ['Gene', 'Belcher'], 
        ['Linda', 'Belcher']]
        
for fname, lname in names:
    print(fname, ' ', lname)

Keep in mind that when you do this, your update variables need to match the number of variables in your sequence. So if we had three variables here, we would get an exception.

Conditions—Python

Most of the time in programming, our programs execute one line at a time. So for example we might see something like this:

name = input('Enter your name => ')  # This statement runs first
print('Hello ', name)  # Now this statement runs next

Sometimes our programs hit a fork in the road and they need to make a decision about the direction they are going to take. Python gives us conditional statements to help make such decision.

A conditional statement is a condition that changes the course of the program’s execution based on a true or false evaluation. Let’s start with a code example to help make this more clear.

gender = 'F'
name = input('Enter your name => ')

if gender == 'F':
    print('Hello Ms. ', name)   # This code only executes for women
                                # (gender == 'F')
else:
    print ('Hello ', name)  # This code executes for anyone else
                            # (gender != 'F')

This code snippet demonstrates a conditional statement. We begin with a variable named gender that is set to the value ‘F’ for female. Ideally, if we know the gender of a person, we should offer the correct greeting for that person.

The if gender == 'F': is the conditional statement. What this statement is doing is using a true/false expression to decide if we should print ‘Hello Ms.’ instead of just the standard ‘Hello’ greeting. If our gender variable is ‘F’, we will print the ‘Hello Ms.’, otherwise we print the ‘Hello’ greeting.

We can handle multiple conditions with the elif keyword. Let’s build on our example:

gender = 'F'
name = input('Enter your name => ')

if gender == 'F':               # First check if the gender is F
    print('Hello Ms. ', name)   # This code only executes for women
                                # (gender == 'F')

elif gender == 'M':             # Now check if gender is M
    print ('Hello Mr. ', name)  # This time print a greeting for men
                                # (gender == 'M')
else:
    print ('Hello ', name)  # This code executes for anyone else
                            # (gender != 'F')

Adding the elif keyword is a way to stack up multiple conditions and define an action for each condition. Now I should point out at this time that elif and else are completely optional. So it is ok to do this:

gender = 'F'
if gender == 'F':
    print('Found female')
print ('Done checking for m/f') # At this point, the code continues
                                # executing normally

We can also check for false conditions by using the != operator.

gendar = 'F'
if gender != 'M':   # Execute the code inside of the if block if
                    # if the gender is not male
    print('Found female')
print('Done checking for m/f') # Return to normal execution
%d bloggers like this: