So let's take a look at the binary search algorithm implemented in Python. Here we are in our lab environment, File, Open because I have prepared this solution here for us. And here is the code. The reading has this code which I'd wrote from the description of the binary search that we've just walked through. And I use the same data set from the graphic. So we're going to search the data set known as the haystack looking for the needle. Left is set to 0, and right is the length of the (haystack)- 1, and while left is less than or equal to right, we're going to do our loop. Here we're calculating the middle. Notice the use of the // because I don't want a floating point for an index, so that forces it to be our integer. Each time through the loop, were going to print out. This is just for pedagogical purposes, were going to print out watch left of the haystack that will search in for our needle. If we have found the needle, we return it, otherwise we just left or right accordingly, discarding the left side or the right side, depending on whether we have found a value that's too low or too high. If we loop through without ever finding it, then will return- 1, if we have exhausted our data set. So here is our sample data set, and what we're going to do is loop over this set were going to look for multiple needles so you can look to see what it looked like to find things. So we're going to look for things that are in the data set. In fact, we're going to look for all the different things that are in the data set, as well as several things that are not. So each time through were looking for a new needle and will do the whole binary search. If the location is greater than or equal to zero were going to say yes, we found the needle in the haystack at this location. Otherwise, we're going to say we couldn't find the needle in the haystack. And for each needle that we searched for when we're done, we're just going to print out a separator. So let's go ahead and run it. And here you see in your lab you're just going to come execute this and look through on your own. And you can read the code and change the values if you want, you could change this to be strings, but remember one of our requirements is that it be sorted. That's why the examples tend to be with numbers, so you can change the numbers up as you want. Same thing you can change up what you might want to look for. But changing it to be strings, you just have to be careful to make sure that they're sorted. Because otherwise, the algorithm doesn't work and I haven't shown you how to sort an array, so initially were looking through the whole data set for 0. Well, it's not the one in the middle, so we cut it in half. And it's not that, so we cut it in there and it's not that, and therefore we couldn't find it. But when we look for one, well we didn't find it in the middle, which was the 23 and we didn't find it at the three. Notice, this is an even number, so there is no middle. We didn't find it at the three, so will check the one in yes, that's where we found it. Will skip all the way down to the last 199. Again, it was looking here at the 23 didn't find it, so it discarded everything below. And search the upper part and discarded this part searched in there didn't find it. Searched here, doesn't find it, can't find so that is our binary search algorithm written quickly and simply in Python. Wasn't looking to optimize how it might work, just trying to get something that reads reasonably. And I think this might be the first time we've used comments in Python, so just to be clear that is a comment. Things that begin with the hash or pound sign are comments. And in our next lesson will talk about an even higher order concept known as a software design pattern.
