And over here, not here, not there.

Acupuncture, nope, still not there.

I'm looking, I'm looking, I'm looking, I'm looking.

Are you getting bored yet?

I'm getting very bored.

I'm not gonna make you watch me page through this dictionary page after page

to find the work shark.

It's way back here at the Ss.

This is gonna take a really long time.

But this is effectively what we were doing with linear search.

We are starting the beginning, looking all the way through in a row, our array.

So what's a better approach to approach this problem?

Well, it's an intuitive parse that we all use when we're opening a dictionary and

trying to find a particular word.

I don't open to the beginning,

because I know us is sort of in the middle towards the end of the alphabet.

So I'm going to open to about sort of halfway, maybe a little bit more.

And I found myself in the Rs.

Okay.

R S, S comes after R.

So I need to go a little bit further, so

I'll take another chunk of the dictionary and flip it over.

Oh, I've gone way too far, I'm now in the Ys.

So let me flip back a little bit, okay.

Now I find myself in the Ts, keep going back.

Great, I'm in the Ss, S O, I need to go back a little bit more.

So on and so forth until I find the word I'm looking for.

And already, after only about three or four flips, I'm much closer to shark.

The word I'm currently looking at is shirt, Than I was when I started the As

and was just flipping through one page after another.

So this is an example of the binary search algorithm.

What I'm doing is is I'm starting with my entire pool of data, in this case,

it's the dictionary, and then I'm going to go half way and

I'm going to reassess where I am to see if I've found the thing I'm looking at.

And if I haven't found the thing I'm looking at,

I'm going to use some information to decide whether I should go to the second

half or go back to the first half, and then I just have a smaller

version of the same problem, where I'll again flip the book open about halfway.

So notice each time I flip, my pages are getting smaller and

smaller and smaller, the number of pages that I flip.

And that's the exact same intuition behind binary search.

So lets step back over now into the code, so

we can figure out how to write this algorithm on the computer.

So we're going to need to implement this algorithm by taking our data in our array

and what we want to do is to cut the list in half each time.

But if you look at the list as it stands right now,

you'll notice a really important difference between the data that's

in this list currently and the data that we had over here in our dictionary.

So think about it for a second, maybe pause the video,

see if you can identify the issue that we have right now.