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

Friday: Writing a Binary Search
This week’s project is all about understanding one of the more efficient algorithms in programming… Binary Search. When you need to search a list full of data, you need to do it efficiently. It may not make sense to create an algorithm for a list of ten items but imagine if it was one million items. You don’t want to search through the list item by item to try and find what you’re looking for. Instead, we use algorithms like Binary Search to perform these tasks.
To follow along with this lesson, let’s continue from our previous notebook file
“Week_08” and add a markdown cell at the bottom that says, “Friday Project: Writing a Binary Search.”

Final Design

Although the program itself will be relatively small, we must understand how the algorithm for Binary Search works. For our design concept this week, we’re going to lay out the steps that we need to follow. Remember that algorithms are nothing more than a set of steps. Binary Search is no different. Each step for this algorithm is as follows:
ChapteR 8 advanCed topICs I: eFFICIenCy

1. 
   Sort the list.
   
2. 
   Find the middle index.
   
3. 
   Check the value at the middle index; if it’s the value we’re looking for, return True.
   
4. 
   Check the value at the middle index; if it’s greater than the value we’re looking for, cut off the right half of the list.
   
5. 
   Check the value at the middle index; if it’s less than the value we’re looking for, cut off the left half of the list.
   
6. 
   Repeat steps 2 through 6 until the list is empty.
   
7. 
   If the while loop ends, it means there’s no items left, so return False.
   

Let’s walk through an example together with the following arguments: [ 14, 0, 6, 32, 8 ], and we’ll be looking for the number 14. See Table 8-1 for a step-by-step walk-through.
Table 8-1. Binary Search example description