Linear search searches for a value on a list starting at index zero. It proceeds linearly through the list until it finds the value. If there are n items in the list, then linear search might look at all n items. For example, if the value is not in the list, then it will examine each item in the list. Linear search works on both sorted and unsorted lists. However, if we know that the list is sorted, we can do much, much better using an algorithm known as binary search. Here is the function header and box string for binary search. Like with linear search, it takes a list and a value and returns the index of the first occurrence of that value in the list, or minus 1 if the value is not in the list. Binary search only works if L is sorted. It turns out that it also only works if each item in L can be compared to v. Here's an example to get you used to the idea. Here, we have a sorted list of numbers and we're searching for 5. We want the first occurrence of 5, the 1 at index 3. Let's draw a dividing line. This line divides the items that are less than v from the items that are bigger or equal to v. Notice that this includes the item in index 3, the 5 that we're looking for. Let's say, we have a list of 100,000 items. We can calculate the middle index pretty easily and we can examine that value. If that middle value is less than the value we're looking for, then because the list is sorted, we know that all of the values to the left of it are also less than the value we're looking for. And therefore, we can eliminate 50,000 items with just one comparison. So, partway through our binary search algorithm, we have three regions in our list. On the left are all the items that are less than v, on the right are all the items that are greater than or equal to v. And in the middle is the unknown section, the items we know nothing about yet. Let's mark the beginning of that unknown section with a variable b and the end of that unknown section with a variable e. When this function is called, we know nothing about any of the values in the list. And so, b will start off at index zero and e will start off at index length of L minus 1. Here's the code. At the end of this process, the unknown section is empty. Everything on the left is less than v, everything on the right is greater than or equal to v. The unknown section is empty. Variable b is to the right of the line, and variable e is to the left of the line. This is what it looks like in the beginning. And this is what it looks like at the end. So, this loop is going to continually march b and e closer to eachother until they cross. In our loop, we'll calculate the midpoint between b and e, then we'll examine it to see if that item is less than v. If it is, we can set i's new value to m plus 1 because all these values are less than v. On the other hand, if the item in index m is grater or equal to v, then we can move e to m minus 1 because all the v's values are grater than or equal to v. Let's write our loop. We'll figure out the loop condition in a moment. But if the item in index is less than v, then we'll going to move b to index n plus 1. And if the item in index 1 is greater than or equal to v, then we'll move i to index n minus 1. And now for the loop condition, in the end, b is greater than e. We continue then as long as b is less than or equal to e, because there are still items in the unknown section. And here's the condition. All that's left is to calculate the value for m. We take the average of two numbers like this. But because we don't want a floating point number, we need to do integer division. This code produces this. But we're not quite done. What if this value isn't v? Well, in that case, we are supposed to return minus 1. We have to be a little bit careful here because all of the values might be greater than or equal to v, or they might all be less than v. If they're all greater than or equal to v, then this section here takes up the entire list. b is on the right, e is on the left, b must be zero. We can look at L [UNKNOWN] zero, that's fine. But, what if they're all less than v? Then, this line ends up over on the right because this whole section takes up the whole list. And in that case, b ends up here, and e ends up there. b is now the length of L and I can't use that as an index. I'll get an index error. I'm going to write a new statement. In one situation, I'm going to return minus 1. That's when v is not in the list. Otherwise, I'm going to return index b. Because if v is on the list, b is going to be the index of the first occurrence of v. I know that one situation where v is now the lowest can be detected by comparing b to length of L. So, if b is the length of L, I want to return minus 1. Or if L at index b is not equal to v, then I also want to return minus 1. If b isn't the length of L, and L at b is equal to v, I want to return index b. Let's write some doc test code. If this module is the one being run, then we'll import doctest, and we'll run our tests. Keep your fingers crossed. And we win.
