The algorithm John used, linear search, seemed familiar to us.

And you could understand it because it's how most of us search for

things in real life anyway.

Britney's approach, on the other hand,

got results quickly, but it was a bit harder to understand.

So let's break it down.

[SOUND] Just like John's approach, Britney started with a series of values, or

list of numbers, as her input.

Where John just started at the beginning of the list and searched sequentially,

Britney's strategy is to always start in the middle of the range.

From there, she asks a comparison question,

is the number in the middle of the range equal to the answer she's looking for?

And if it's not, is it greater than or less than the answer?

If it's greater than,

she can eliminate all the values less than the one she's currently evaluating.

If it's lesser than the answer,

she can eliminate all the values greater than the one she's currently evaluating.

With the range of values that she's left over with,

she repeats this process until she arrives at the answer.

[SOUND] Let's visualize how she did this by looking at Round 3.

[SOUND] In Round 3, the number of values in the range was 100.

The answer was 5.

The bar here represents the range of values, 1 on the left, 100 on

the right and this pointer represents the value Britney chooses to evaluate.

So she starts in the middle at 50, she asks is it equal to the answer?

I say it's too high.

So this tells her that the value she is evaluating is greater than our target

value.

Which means there's no point in searching any of the values to the right of 50,

that is values greater than 50 in this range.

So she can discard those values altogether.

[SOUND] She only has to consider values from 1 to 50 now.

[SOUND] The beauty of this strategy, and

the reason why Britney was able to find the answer in such few turns,

is that with every value she evaluates, she can discard half of the current range.

On her second turn, [SOUND] she picks the value in the middle of the current range,

which is 25.

She asks the same question.

I say that the value is too high again.

And this tells her that she can discard everything greater than 25.

[SOUND] And the range of value drops from 1 to 25.

Again, she evaluates the number in the middle, roughly.

So that'd be 13, here.

I tell her, this is still too high.

She discards the values greater, moves to value 7, which is still too high.

Then she moves to 4, which is now too low.

She can discard everything less than 4, which leaves the numbers 4 through 7.

Here, she picks 6, which is too high, which only leaves one value, 5.

This seems like a lot of work.

But being able to get rid of half the values with each turn

is what makes this algorithm much more efficient.

Now, there's one subtlety to using binary search, and

you might have caught on to this.

For this search method to work, as we've mentioned, the values need to be sorted.

[SOUND] With linear search, it doesn't matter if the values are sorted.

Since a linear search algorithm just progresses sequentially,

checking every element in the list.

If the target value exists in the list, it will be found.

Let's say this range of values, 1 to 100, was unsorted.

Britney would start at the middle with something like 14 and

ask if this value was too low or too high?

I say it's too high so she discards everything less than 14.

Now, this example starts to fall apart here, because well,

Brittany knows what numbers are less than 14 and greater than 1.

She doesn't need an actual range of values to solve this.

A computer, however, does need that.

Remember, search algorithms are run against lists containing all sorts

of data.

It's not always just a range of values containing numbers.

In a real use case of binary search, which we're going to implement in a bit.

The algorithm wouldn't return the target value because we already know

that it's a search algorithm.

So we're providing something to search for.

Instead, what it returns is the position in the list that the target occupies.

Without the list being sorted,

a binary search algorithm will discard all the values to the left of 14 which over

here could include the position where our target value is.

Eventually we get a result back saying the target value doesn't exist in the list

which is inaccurate.

Earlier when defining linear simple search I said that the input was a list of

values and the output was the target value or

more specifically the position of the target value in the list.

So at binary search there's also that pre-condition the input list must be

sorted.

So let's formally define binary search.

First the input a sorted list of values.

The output,

the position in the list of the target value we're searching for, [SOUND] or

some sort of values indicate that the target does not exist in the list.

Remember our guidelines for defining an algorithm?

Let me put those up again really quick.

The steps in the algorithm need to be in a specific order.

The steps also need to be very distinct.

The algorithms should produce a result and

finally the algorithms should complete in a finite amount of time.

Let’s use those to define this algorithm.

Step one, [SOUND] we determine the middle position of the sorted list.

Step two, we compare the element in the middle position to the target element.

Step three, if the elements match, we return the middle position and end.

[SOUND] If they don't match, in step four, we check whether the element in

the middle position is smaller than the target element.

[SOUND] If it is, then we go back to step two, with a new list that goes from

the middle position of the current list to the end of the current list.

[SOUND] In step five, if the element in the middle position is greater than

the target element, then again [SOUND] we go back to step two.

With a new list that goes to the start of the current list to the middle

of the current list.

[SOUND] We repeat this process until the target element is found.

Or until a sub-list contains only one element.

If that single element sub-list does not match the target elements,

then we end the algorithm.

Indicating that the element does not exist in the list.

Okay, so

that is the magic behind how Britney managed to solve around much faster.

In the next video let's talk about the efficiency of binary search