Binary Search Algorithm - Python Example & Code

Key Takeaways

[Music] welcome back to another YouTube video so in today's video I'm going to be talking about the binary search algorithm now in the last video we talked about the linear search algorithm a very simple algorithm pretty much if this was our list it looks around the beginning to the end of the list until it found the element that we were looking for this search algorithm is much faster especially on large data sets and it has log n Big O notation meaning that it gets exponentially faster as the data set gets larger so this is extremely useful and it's a lot more useful than the linear search has more applications so let's get right into how it works so this is gonna be a list up here just for example purposes I know it's extremely simple but it's just easy to illustrate how things work with a small list now binary meaning 2 means that we're gonna have two main comparisons in this in this search it's gonna be greater than and less than so what we're gonna do is we're gonna find the middle indicee this what the algorithm does finds the middle indicee or index of the list which in this case would be 5 now it's gonna compare the element where that we're looking for and right now we're gonna be looking for one to this element it's gonna say is 1 greater than 5 no it's not is 1 lesson 5 yes it is now once we know this information we then split up the list or the algorithm splits up the list so if we know that 1 is less than 5 why would we continue to look this way if we know it's gonna be in the bottom half of the list so now we have a list of 1 2 3 4 and the same process repeats itself so now we have this list and we're gonna look at the middle indices now notice this is not an odd numbered list so because of this the industry we're going to be checking is here it doesn't really matter which one you check if you check this one or this one we're just gonna be checking this one and then we're gonna say well is 1 less than 2 yes it is so now we create a list that only has 1 in it and then we find that since there's only one element in it and that's the element we're checking that is 1 all right so I know I went kind of fast a little bit confusing but as I go through the code of this algorithm you'll understand hopefully how this works so this is my function here it's not too complex and it is fairly simple to code so we're gonna start off by sorting our list so I mentioned that this algorithm only works if the list is sorted and obviously that's because if we have these in different orders we wouldn't be able to do the same comparisons that we're doing in the algorithm now we start by setting two variables a top and a bottom variable so our top is gonna be the top section of the list and the bottom is gonna be the bottom of a section list and rather than recreating a bunch of different lists every time we we split it up or we do a comparison we're just gonna be looking at a different part of the list so rather than recreating a list which gonna take more time and more memory we're just looking at a different section of the original list that makes sense so we have our top our bottom this is gonna be the whole list because we start at 0 and we go to the last in the scene and then here I just print this out just so we can see we'll be able to see when we run the program and now we find our middle indicee in this while loop so this middle indicee is gonna be the top plus the bottom / - just how you find example midpoint of a line or the middle of a list and this integer division is very important because if we get something like we have 5 for example and we divide by 2 then we're gonna be getting in decimal number which we don't want all right and then we do our comparisons so we start by checking well is the element that we're looking for right here equal to the element in the list that we're comparing it to so pretty much the 1 step here so once we check the middle indicee we're gonna first see well if the element that we're looking for is equal to that middle indicee we've now found it we don't need to continue to look through the list if it's not equal to that then we move down and we say well is it less than the middle indices or whatever that element is if it is then we're gonna be setting our top to our middle and what that does is it moves pretty much at the top is here at 9 it moves it down to 5 so that we can then look through the next section of the list like that and then the next part here so we say if element is greater than and then same thing so we're gonna move our bottom to the middle so what we do is we have this is our bottom we would then move it up here so now the next section of our list is this and you can see how this continues to go on now it is to be noted here I could just put an else statement the reason I put Elif is just to illustrate more clearly exactly how this works because obviously if it's not equal to it's not less than it's gonna be greater than if it's a number and this does work for strings in Python so in Python you can actually I'll show you down here you could actually do for example something like this like that and that would actually work as a comparison it's really weird compared to other languages but it does work so you can compare strings like that so this will work for Strings if you're using Python and then down here this is just where I create a random list of integers and then I just select a random integer to look for it in the list so if we go ahead and run the program here save it then you can see I just simply am printing out the length of the list to show you how many comparisons were actually doing so we start with ten thousand five thousand 2500 1250 so on having each time now as we get down to the end here we have ten elements left and at this point we've now found the element we're looking for which is at the twelve hundred and fifteenth index now this is extremely efficient and you can see already that if I had tried to do ten thousand items in a linear search and say maybe we got unlucky and the item we were looking for was at the very end we would still be waiting for that search to go on so you can see how much faster this actually gets now if I just add another zero here tour at the length of our list a hundred thousand we can run it again and you see we're going it's extremely fast considering the amount of items in our list if I'm not if I don't print this it should pop up almost instantly oops comment that out and yeah you can see we get that almost instantly now again if we go to 1 million there we go we're getting hit again almost instantly 10 million let's see how fast this one goes and we're taking a little bit longer on this one which is to be expected so yeah you can see that the binary search is extremely efficient and it's obviously better to use a linear search if you're using longer or larger data sets the reason we would use linear search over this is only because of this aspect right here if you look if you're looking at a small data set and you don't want to sort it first then you just use a linear search so yeah this has been the video on the binary sorry not sort search algorithm I've just been saying sort for a long time now haven't I I hope you guys enjoyed if you did please leave a like and subscribe and I will see you again [Music]