Python Projects for Beginners a ten-Week Bootcamp Approach to Python Programming

Program Setup

Before we begin to write our algorithm, we need to set up a way to generate a random list of numbers. Let’s import the random module and use list comprehension to generate some data:

1| # setting up imports and generating a list of random numbers to work with 2| import random
4| nums = [ random.randint(0, 20) for i in range(10) ] # create a list
of ten numbers between 0 and 20
6| print( sorted(nums) ) # for debugging purposes

Go ahead and run the cell. We import the random module in order to generate a list of 20 random numbers with our list comprehension. For debugging purposes, we output a sorted version of nums on line 6 in order to see the data that we’ll be working with.

Step 1: Sort the List

The first step in the algorithm is to sort the list. Generally, you sort the list before passing it in, but we want to take all precautions that this algorithm works even with unsorted lists. Let’s begin by defining the function definition, as well as sorting the list passed in:

4| nums = [ random.randint(0, 20) for i in range(10) ] # create a ... ◽◽◽ 6| def binarySearch(aList, num):
7| # step 1: sort the list
8| aList.sort( )
10| print( sorted(nums) ) # for debugging purposes
12| print( binarySearch(nums, 3) )

We’ve added the function call at the bottom and will be printing the returned value, but for now nothing will happen when you run the cell. Let’s move on to step 2.

Step 2: Find the Middle Index

In this step, we need to find the middle index. I’m not talking about the value of the item in the middle of the list but rather the actual index number. If we’re searching a list of one million items, the middle index would be 500,000. The value at that index could be any number, but again, that’s not what this step is for. Let’s write out the second step:

8| aList.sort( ) ◽◽◽
10| # step 2: find the middle index
11| mid = len(aList) // 2 # two slashes means floor division – round down to the nearest whole num
13| print(mid) # remove once working
15| print( sorted(nums) ) # for debugging purposes ◽◽◽

Go ahead and run the cell. In order to find the middle index, we need to divide the length of the list by two and then round down to the nearest whole number. We need to use whole numbers because an index is only ever a whole number. You could never access index 1.5. Also, we round down because rounding up would cause index out of range errors. For example, if there is one item within the list, then 1 / 2 = 0.5 and rounding up to one would cause an error, as the single item within the list is at index zero. The output will result in 5, as we’re working with a list of ten numbers. Go ahead and remove the print statement at line 13 when you’re done.