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.