Transcript:
Alright, so, in this video, we’ll be going over the binary search algorithm in Python, we’ll be covering both an iterative and recursive version of binary search. And if you’re not familiar with what binary search is basically, it allows you to very quickly determine whether or not an element that you’re looking for is in a list of elements that are sorted. So for example, we have a list here, which is called data and this is just an assortment of integers that having to be sorted and the problem statement is given a list and given an element that we’re looking for which is usually called the target lets. Just say the targets. I don’t know 28 so given a list and a target. We want to determine whether or not the target is present in the list so before we actually go through the binary search algorithm. I want to just think about how we can solve this problem. In a more straightforward approach or something that might immediately become obvious in terms of a way to solve the problem, so one obvious approach that you can use is you can just look at the list and you can consider each element individually and loop through the entire thing until you find the element or until you reach the end of the list where you don’t encounter the element. So this approach roughly is called linear search, so we’re going through each element in the list we’re asking is this element that we’re on the item that we’re looking for if it’s not we continue and otherwise we if we encounter the element that we’re looking for we stop or if we reach the end of the list, we stop because the element is not in the list, so let’s just code that up really quickly, just so we can see exactly how one would perform something like this, so I’m going to create a function for this particular search. I’m just going to call it layer search, and it’s a function that’s going to take the list and also the element that we’re looking for, and the algorithm itself is fairly straightforward. All we really want to do is loop through the list, so I’ll say for I range like the data, and then what we’re gonna do in this list is really just one check, which is the element that we’re on in the loop equal to the element that we’re looking for if it is that we exit out of the loop and that’s that we found the element. Otherwise, if we go through the entire list, we haven’t found anything. We know that the element is not in the list again because it’s sorted. It will just return false, so linear search is not horrible, but it’s a linear time algorithm, so it’s going to perform in the worst case in linear time because you have to, at the very least of the elements, not in the list. You’re going to have to iterate through each element in the list before you determine that the element is not present, So for instance, if I put it something like 50 or 690 or anything like that, Then I would have to go through the entire list before I would realize that 50 was not in the list. If for using this particular approach, so binary search is a way that we can solve this problem and we can solve it using login time, so it’s quite a bit better just to give you some context. If you have a list of, let’s say a billion entries, login of a billion is 30 so it will take you essentially 30 operations to determine whether or not an element is on the list so quite a bit better than N, which in that case would be a billion so quite an improvement, so let’s actually just step through that binary search algorithm and what we’re going to do is we’re going to start with the Iterative version because it’s maybe a little bit straightforward. If you’re not familiar with recursion, so what I’m going to do is I’m going to make a comment here, type out iterative binary search and I’ll also define a function for this as well so binary search iterative. It takes in the same parameters as we had for linear search a list and also a target, which is the element that we’re looking for And what we’re gonna do what the general approach of binary search is is we can contain. We can take advantage of the fact the list that we have is sorted again. This is a very important prerequisite of being able to effectively use binary search because essentially what we’re gonna do is we’re going to break the problem down kind of divide and conquer the problem. We’re going to ask whether or not the element that we were gonna split the list in half first of all, look at the middle element and ask is the element that we’re looking for greater than or less than the element that we’re looking for, so if it’s greater than we know that the element that we’re looking for must be in the upper half of the array, likewise, if it’s less than we know that it must be in the less in the in the lower half of the array again, we can make this assumption because we are given that the entries in this list are sorted, so what we’re going to do is we’re going to have two variables that we’re going to declare at the beginning, low and high, which are going to initially correspond to the first element in the list. The index of the first element and high will correspond to the index of the last element in the list, minus one and so generally what we’re gonna do to break this problem down is we’re going to have a while loop. So while low is less than or equal to high, we’re gonna do essentially the main binary search algorithm, like I said, before we’re going to compute the middle element we’re going to determine what the middle element in the list is and we can do that. By just saying, low + high divided by two so again we’re taking the index of zero, so the beginning of the list, along with the length of the list minus one we’re adding those two things together were divided by two. That’s going to give us the middle element of the list and then what we’re going to do. Is we’re going to check right off? The bat is the target is the item that we’re looking for actually just equal to the middle element of this list. If it is that we can return true, so we’re going to write that out here. So if target is equal to the middle element of the list, then we’ll just return true that we found. We found the element that we’re after so this is this we’re gonna have an else If and in else where essentially we consider either the top portion that is the portion of the array after the middle element or the bottom portion that is the portion of the array or the list below the middle element, so if else if the target is less than the element at the middle point, so if this is true, that we’re going to essentially shift where our high point is so now our high point is going to be where the middle wise minus one, so we’re gonna say hi is equal to bid minus one, so essentially what that is is. If we take a look at this list, let’s say we’re looking for five. So if the target that we’re looking for is less than the middle point. I don’t exactly know where the middle point is in this array, lets. Just say it’s here So basically what I’m gonna do is I’m going to throw out this whole chunk of the array. I don’t even care about it because I know that five can’t be above the middle point, which, in this case was 17 it must be in the lower part of the array, so I’m going to reassign the top of the list high equal to the mid point, which was 17 and then low stays the same. So I’m going to undo that because I want to keep the list as it was. So that is what’s going on in this line here, so you can imagine that in the other case where the element that we’re looking for is greater than the mid point we’re gonna do the same thing only we’re going to reassign the low point to the array. So for instance, let’s say the element that we were looking for is 25 again if we assume that 17 was their midpoint in this array, what we could do is we could say, OK? It’s greater than the target that we’re looking for is greater than what is at the middle. So kill everything here, we don’t care about it. We’ve eliminated half of the list that we don’t even need to look at now and we know it must be in this upper portion of the list and we just continue from there. So what we do is we say else. Low is now equal to the big void plus 1 so we just do this in the while loop, and if we go through this entire loop without finding the element that we’re looking for the element is not in the list. Otherwise, we found the element, so the this this if condition will hit true and this, this condition won’t return true, we’ll find the element that we’re after so this is let me just put in the final return. False here, which is what? I’m missing so this is the Standard Iterative version of binary search, and if you are planning on doing a technical interview at company, I encourage you to just, you know, tattoo this on your face. This is a very important algorithm that you should have down cold and that you should be able to recall with your eyes closed heads tied behind your back and all that good stuff. So make sure you understand this algorithm. Make sure you can work through it in your sleep. It’s pretty short, it’s pretty intuitive, which is nice, but there are some things that can really trip you up. If you’re recalling this, let’s say wrote from memory, a few things that are just edge cases, which are kind of tricky. If you were to write this up, you might forget, for instance, that this minus one is important. You might forget that let’s say that’s. Its bid minus 1 here mid plus 1 here again. If you work through exactly what binary search is doing if you understand the idea those things should become apparent, but in the context of an interview. You really want to make sure that you just have this down? OK, that’s the end of the rant. It’s not worth the Arats, but the end of the statement, so now what we’re gonna do is we’re going to look at a recursive version of binary search. So this is the same idea, the same algorithm only we are not going to use a loop. We’re going to use recursion, so let me just write out recursive binary search, and I’m going to define the prototype of the function binary search recursive, and in this case, the the prototype. The number of our group arguments in this all in this function are going to be a little bit different, so we’re still going to have the data and a target, but since this function is going to call itself and it’s going to need to keep track of the the low of the high points, we’re also going to pass those in to this to this function, so in addition to the list and the target we’re also going to pass in the low and high parameters as well. So the first thing that we’re going to do is we’re going to check whether or not the low point is greater than the high point. Because if that’s the case, we’ve kind of crossed paths on the array. It’s the base case in this recursive approach. So if this essentially this condition is true, we know that we’ve could have crossed the point of no return and the element that we’re looking for in the list is not present. So this is the base case of a recursion as that the else condition is going to be. The is the meet of the recursive binary search algorithm so just like before we’re going to compute the middle element of the list in the same exact manner that we did before we’re going to say beta is equal to hi. Sorry, lo plus, hi, divided by two, and then what we’re going to do is we’re going to again, Follow a pretty similar approach to what we had before. If the target is equal to the element at the midpoint, then we’re going to return true, just like before Elsif here. The target is less than data admit, we’re going to do something and then the other else condition here we’re going to do something else so just like we had this else. If an else condition in the iterative version of binary search, there’s going to be kind of a similar type of an idea here for the recursive version, as well, so for the recursive version of whether what the target is less than the element at the midpoint. What we want to do is what to return Binary search. Recursive data stays the same because we’re not changing the list target. It’s still the element that we care about that we’re looking for, but we’re going to reassign the highpoint, so lo stays the same, and then mid- one eye comes the new high point, just like here, the inert of case where we cite the high point to be mid minus one. We’re just passing that into the recursive call, so that way when the binary search recursive call is called again, it’s called with low being the same and the high is now bid minus one. So you can guess what we could do in this. In this else, condition as well, so it’s basically the same thing. Binary search, recursive data target, and now mid plus one because we’ve moved up from where we need to be and then high stays the same, so that is the end of the recursive version of binary search and just to make sure that this actually does what we expect it to do. Let’s go ahead and print out calls to both of these functions so to say print’s, binary search iterative and it also prints, binary search recursive, so in the Internet version. We all need to pass up the data at the target, which is a recall we defined up at the top in this case. The target. I’m just going to keep this 25 The recursive version of binary search again takes the target and the data as well in addition to where we’re going to start at the low point and the pipe flights. So in this case, this is the length of the list minus 1 So if we print this out, let’s see. I think I have forgotten an equal sign here, so if we print this out, we’re getting true for both of these things, which is good if we had disagreement about our different implementations of the same algorithm that would be a little bit unsettling, but it does indeed to tell us that the element that were after 25 is present in this list and indeed this list is small enough to see that the list. The item is there, so that’s? The end of this lesson on binary search just wanted to do a very quick implementation of both the iterative and recursive versions. I will as always be posting the code up on my Github. The link will be provided in the description below and. I hope this was helpful to you. Please make sure that you are able to reconstitute this function on the spot if you need if you need to the context of a technical interview because I guarantee that this problem will most likely come up in some form, maybe not in this exact form, but knowing that you can apply this technique and how to actually get it down on paper is really important, so thanks again for watching and have a great day you.