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

Step 7: Return False Otherwise

To complete our Binary Search, we simply need to return False after the while loop ends:

19| aList = aList[ mid + 1 : ] ◽◽◽
21| # step 7: return False, if it makes it to this line it means the list was empty and num wasn’t found
22| return False
24| print( sorted(nums) ) # for debugging purposes ◽◽◽

Go ahead and run the cell. We’ve now completed the Binary Search algorithm! Now when you run the cell, you’ll get an output of either True or False. Feel free to print out the list within the while loop, so you can see how the list is being truncated on each step.

Final Output

You can find all the code for this week, as well as this project in the Github repository. The final output in the following won’t include any of the comments we added in previous blocks so that you may see the complete version unobstructed:

1| # full output of binary search without comments
2| import random
4| nums = [ random.randint(0, 20) for i in range(10) ] 6| def binarySearch(aList, num):
7| aList.sort( ) 9| while aList:
10| mid = len(aList) // 2 12| if aList[mid] == num:
13| return True 14| elif aList[mid] > num:
15| aList = aList[ : mid ] 16| elif aList[mid] < num:
17| aList = aList[ mid + 1 : ]
19| return False
21| print( sorted(nums) )
22| print( binarySearch(nums, 3) )

Go ahead and run the cell. If you ran into any problems, be sure to reference this code. Try increasing the number of items within the list you pass in and see how quickly it can find your number. Even on large lists, this algorithm will execute with extreme speed.
today was important in understanding not only how Binary search works, but how we can program an algorithm from a set of step-by-step instructions. algorithms can be simple to understand, yet difficult to translate into code. Using this algorithm, we can begin to understand how searches can be efficient, even when there are large amounts of data to sift through.
Weekly Summary
Throughout this week, we were able to go over some of the more advanced topics within Python. As you begin to build your programming experience, you should always be thinking about efficiency. First and foremost, we need to make sure that our programs are correct in their execution, but then we need to be aware of their speed. If an algorithm or program could give you the price of a stock to the cent, but it took ten years to execute, it would be worthless. That’s the importance of a great algorithm. Along with efficiency, we want to keep in mind the readability of our code. Although sing list comprehension, lambdas, and recursive functions don’t improve the speed of our program, it helps to improve our ability to read what’s happening. During the lessons next week, we’ll be covering algorithmic complexity and the importance of performance when using certain data types.