Binary Search in Code10:03 with Pasan Premaratne
In the last video we left off with an implementation of linear search. Let's do the same for binary search so that we get an understanding of how this is represented in code.
In the last video, we left off with an implementation of linear search. 0:00 Let's do the same for binary search so 0:04 that we get an understanding of how this is represented in code. 0:06 So we'll do this in a new file, back to File, New File. 0:10 And we'll name this one binary_search.py. 0:14 Like before, we're going to start with a function named binary search. 0:20 So we'll say def binary_search. 0:24 That takes a list and a target. 0:27 If you remember, binary search works by breaking the array or 0:31 list down into smaller sets until we find the value we're looking for. 0:35 We need a way to keep track of the position of the lists that we're 0:39 working with. 0:43 So let's create two variables, first and 0:44 last to point to the beginning and end of the array. 0:47 So, first = 0. 0:50 Now, if you're new to programming, 0:54 list positions are represented by index values that start at 0 instead of 1. 0:56 So here, we're setting first to 0 to point to the first element in the list. 1:00 Last is going to point to the last element in the list. 1:06 So we'll say, last = len(list)- 1. 1:09 Now, this may be confusing to you, so a quick sidebar to explain what's going on. 1:15 Let's say we have a list containing five elements. 1:20 If we called len on the list, we should get five back, 1:23 because there are five elements. 1:25 But remember that because the position number start at zero, 1:27 the last value is not at position five, but at four. 1:31 In nearly all programming languages, getting the position of the last element 1:35 in the list is obtained by determining the length of the list and deducting 1, 1:40 which is what we're doing. 1:44 Okay, so we know where the first and last positions are when we start the algorithm. 1:46 For our next line of code, we're going to create a while loop. 1:51 A while loop takes a condition and 1:54 keeps executing the code inside the loop until the condition evaluates to false. 1:57 For our condition, we're going to say to keep executing this loop 2:02 until the value of first is less than or equal to the value of last. 2:07 So while first less than or equal to last, why you ask, why is this our condition? 2:12 Well, let's work through this implementation and 2:20 then a visualization should help. 2:23 Inside the while loop, we're going to calculate the mid point of our list since 2:24 that's the first step of binary search. 2:29 Mid point equal, so we'll say first plus last, and 2:32 then we will use the floor division, // here, divided by 2. 2:36 Now the two forward slashes here are what Python calls a floor division operator. 2:42 What it does is it rounds down to the nearest whole number. 2:48 So if we have eight element array first is zero, last is seven, 2:51 if we divided 0+7, which is 7 by 2, we'll get 3.5. 2:56 That 3.5 is not a valid index position so you round the dot to 3, 3:02 using the floor division operator. 3:06 Okay, so now we have a midpoint. 3:08 The next step of binary search is to evaluate whether the value at this 3:10 midpoint is the same as the target we're looking for. 3:14 So say if list, and value it midpoint, equals the target. 3:17 Well if it is, then we'll go ahead and return the midpoint. 3:24 So say return midpoint. 3:28 The return statement terminates our algorithm, and over here we're done. 3:31 This is our best case scenario. 3:35 Next, we'll say else if list at midpoint, or 3:39 a value at midpoint, is less than the target? 3:43 Now here, if the value is less, the value at midpoint is less than the target, 3:47 then we don't care about any of the values lower than the midpoint. 3:52 So we redefine first to point to the value after the midpoint. 3:56 So we say midpoint+1. 4:01 Now if the value at the midpoint is greater than the target, 4:04 then we can discard the values after the midpoint and 4:08 redefine last to point to the value prior to the midpoint. 4:11 So we say else: last = midpoint- 1. 4:15 Let's visualize this. 4:23 We're going to start with a list of nine integers. 4:24 To make this easier to understand, 4:27 let's specify these integers to be of the same value as its index position. 4:29 So we have a range of values from zero to eight. 4:34 Our target is the worst case scenario. 4:37 We're looking for the position of the value 8. 4:39 At the start, our algorithm sets first to point to be indexed 0 and 4:42 last to point to the length of the list minus 1 which is 8. 4:47 Next, we hit our while loop. 4:51 The logic of this loop is going to be executed as long as the value of first is 4:53 not greater than the value of last. 4:58 Or as we have defined it, we're gonna keep executing the contents of 5:00 the loop as long as first is less than or equal to last. 5:05 On the first pass, this is true, so we enter the body of the loop. 5:08 The midpoint is first plus last divided by 2 and rounded down, so 5:13 we get a nice even 4. 5:17 The value at this position is 4. 5:19 Now, this is not equal to the target, so 5:21 we move to the first else/if for is less than 8. 5:24 So now we redefine first to point to midpoint plus 1, which is 5. 5:27 First is still less than last, so we run through the body of the loop again. 5:33 The midpoint is now 6. 5:38 6 is less than 8, so we move first to point to 7. 5:40 7 is still less than or equal to 8, so we go for another iteration of the loop. 5:45 The midpoint is 7, oddly enough, and 7 is still less than the target. 5:51 So we move first to point to 8. 5:55 First is equal to last now. 5:58 But our condition says keep the loop going as long as first is less than, 6:00 or equal to last. 6:06 So this is our final time through the loop. 6:07 The mid-point is now 8, which makes the value at the mid-point equal to the target 6:10 and we finally exit our algorithm and return the position of the target. 6:15 Now, what if we had executed all this code and 6:20 never hit a case where midpoint equal the target? 6:22 Well, that would mean the list did not contain the target value. 6:26 So after the while loop, at the bottom, we'll return None. 6:29 We have several operations that make up our binary search algorithm, so 6:35 let's look at the run time of each step. 6:39 We start by assigning values to first and last. 6:42 The value assigned to last involves a call to the len function to get the size of 6:46 the list. 6:51 But we already know this is a constant time operation in Python so 6:51 both of these operations run in constant time. 6:56 Inside a loop, we have another value assignment, and 6:59 this is a simple division operation. 7:02 So again, the runtime is constant. 7:04 In the next line of code, we're reading a value from the list and 7:06 comparing the midpoint to the target. 7:10 Both of these again are constant time operations. 7:13 The remainder of the code is just a series of comparisons and value assignments and 7:16 we know that these are all constant time operations as well. 7:21 So if all we have are a series of constant time operations, 7:25 why does this algorithm have, in the worst case, a longer rhythmic run time. 7:28 It's hard to evaluate by just looking at the code, but 7:33 the while loop is what causes the runtime to grow. 7:37 Even though all we're doing is a comparison operation, 7:40 by redefining first and last over here, or 7:44 rather in the last two steps over here, we're asking the algorithm to 7:47 run as many times as it needs until first is equal or greater than last. 7:52 Now each time the loop does this, the size of the data set, the size of the list, 7:58 grows smaller by a certain factor, until it approaches a single element, 8:02 which is what results in the logarithmic runtime. 8:07 Okay, just like with linear search, let's test that our algorithm works. 8:10 So we go back to linear_search.py, and we're going to copy paste. 8:16 So, Cmd+C to copy if you're on Mac, 8:20 then go back to binary search, and at the bottom, oops! 8:23 We're going to paste in that verify function. 8:27 Okay, we'll also go back and grab these numbers. 8:30 You know what, let's go ahead and copy all, all of these things, 8:34 so numbers and the two verified cases. 8:38 We'll paste that in as well, and the only thing we need to change here is, 8:40 instead of calling linear search, this is going to call binary search. 8:44 Okay, we'll hit Cmd+S to save the file, and then I'm going to drag 8:50 up my console and we'll run python binary_search.py and hit Enter. 8:56 And you'll see, just like before, we get the same results back. 9:01 Now, note that an extremely important distinction needs to be made here. 9:05 The numbers list that we've defined for our test cases, 9:09 right here, has to be sorted. 9:13 The basic logic of binary search relies on the fact that if the target is greater 9:16 than the midpoint, then our potential values lie to the left, or vice versa. 9:22 Since the values are sorted in ascending order. 9:27 If the values are unsorted, our implementation of binary search 9:30 may return none, even if the value exists in the list. 9:35 And just like that, you've written code to implement two search algorithms. 9:39 How fun was that? 9:42 Hopefully, this course has shown you that it isn't a topic to be afraid of, and 9:44 that algorithms, like any other topic with code, can be broken down and 9:48 understood piece by piece. 9:53 Now, we have a working implementation of binary search. 9:54 But there's actually more than one way to write it. 9:58 So in the next video let's write a second version. 10:00
You need to sign up for Treehouse in order to download course files.Sign up