DAVID MALAN: Recall that an algorithm is just step-by-step instructions

for solving some problem.

Not unlike this problem here wherein I sought Mike Smith among the whole phone

book of names and numbers.

But up until now, we've really only focused

on those step-by-step instructions and not

so much on how the data we are searching is stored.

Of course, in this version of that problem, it's stored here on paper,

but in the digital world, it's of course not going to be paper, but 0's and 1's.

But it's one thing to say that the numbers and maybe even the names

are stored ultimately as 0's and 1's, but where and how exactly?

There's all those transistors and they're flipping on and off,

but with respect to each other, are those numbers laid out left to right,

top to bottom, are they all over the place?

Let's actually take a look at that question now

and consider how a computer leverages what

are called data structures to facilitate implementation of algorithms.

Indeed, how you lay out a computer's data inside of its memory

has non-trivial impacts on the performance or efficiency

of your algorithms, whereas the algorithm itself

can be correct as we've seen, but not necessarily efficient logically.

Both space and the representation underneath the hood of your data

can also make a significant impact.

But let's simplify the world first.

And rather than focus on, say, a whole phone book of names and numbers,

let's focus just on numbers, and much smaller numbers that aren't even

phone numbers, but just integers, and only save seven of them at a time.

And I've hidden these seven numbers, if you will,

behind these seven yellow doors.

And so by knocking and opening, one of these doors

will reveal one number at a time.

And the goal at hand, though, is to find a very specific number,

just like I sought one specific phone number before, this time I want

to find the number 50 specifically.

Well, where to begin?

I'll go with the one closest to me and knock, knock, knock--

15 is the number.

So a little bit low.

Let's proceed from there to see 23.

We seem to be getting closer.

Let's open this door next and-- oh, we seem to have veered down smaller,

so I'm a little confused.

But I have four doors left to check.

So 50 is not there and 50 is not there and 50 is, in fact, there.

So not bad.

Within just six steps, have I found the number in question.

But of course, to be fair, there were only seven doors.

So if we generalize that to say that there were n doors where n is just

a number, well that was roughly n doors I had to open among the n doors

just to find the one that I sought.

So could I have done better?

You know, my instincts like yours were perhaps to start at the left

and move to the right, and we seem to be on a good path initially.

We went from 15 to 23, and then darn it if 16

didn't throw a wrench in the works, because I expected it,

perhaps naively, to be bigger and bigger as I moved right.

But honestly, had I not told you anything-- and indeed I did-- then

you wouldn't have known anything about these numbers other than maybe

the number 50 is actually there.

I told you nothing as to the magnitude or the size

of any of the other numbers, let alone the order,

but in the world of the phone book, of course,

we were able to take for granted that those names were

sorted by the phone company for us-- from left to right, from A to Z.

But in this case, if your data is just added to the computer's memory one

at a time in no particular order, the onus

is on you, the programmer or algorithm, to find that number

you're interested in nonetheless.

Now what was left here?

And indeed 4 is even smaller than 50.

So these seven doors were by design randomly assigned a number.

And so you could do no better.

I might have gotten lucky.

I might not have gone with my initial instincts

and touch the number 15 at left.

I might have, effectively blinded, gone and touched 50 and just gotten lucky,

and then it would have been just one step.

But there's only a one in seven chance I would have been correct so quickly,

so that's not really an algorithm that I could

reproduce with the same efficiency again and again.

So how can I do better?

And how does the phone company enable us to do better?

Well they, of course, put in a huge amount of effort upfront

to sort all of those names and associated numbers from left

to right, from A to Z. And so that's a huge leg up for us,

because then I can assume I can do divide and conquer or so-called binary

search, dividing that phone book in two as

implied by "bi" in "binary," having the problem again and again.

But someone's got to do that work for us, be it the phone company

or perhaps me with these numbers.

So let's take one more stab at this problem,

this time presuming that the seven doors in question

do, in fact, have the numbers behind them sorted from left to right,

small to big.

So where to find the number 50 now?

I have seven doors behind which are those same numbers,

but this time they are sorted from left to right.

And no skipping ahead thinking that, well, I remember all the other numbers,

so I know immediately where 50 is.

Let's assume for the moment that we don't know anything

about the other numbers other than the fact that they are sorted.

Well, my inclination is not to start at the left with this first door,

much like my inclination ultimately with that phone book was not to start

with the first page, but the middle.

And indeed, I'm going to go here to the middle of these doors and--

16.

Not quite the one I want.

But if the doors are sorted now, I know that that number 50 is not to the left,

and so I'm going to go to the right.

Where do I go to the right?

Well, I have three doors left, I'm going to follow the same algorithm

and open that door in the middle and-- oh, so close.

I found only, if you will, the meaning of life.

So 42, though, is not the number I care about,

but I do know something about 50-- it's bigger than 42.

And so now, it's quite simply the case that-- aha, 50 is there,

it's going to be in that last number.

So whereas before took me up to six steps to find the number 50,

and only then by luck did I find it where

it was because it was just randomly placed,

now I spent 1, 2, 3 steps in total, which is, of course, fewer than six.

And as these numbers of doors grow in size

and I have hundreds or thousands of doors,

surely it will be the case just like the phone book that having this problem

again and again is going to get me to my answer

if it's there in logarithmic instead of linear time, so to speak.

But what's key to the success of this algorithm-- binary search--

is that the doors are not only sorted, but they are back-to-back-to-back.

Now I have the luxury of feet and I can move back and forth

among these numbers, but even my steps take me some amount of time and energy.

But fortunately, each such step just takes one unit of energy, if you will,

and I can immediately jump wherever I would like one step at a time.

But a computer is purely electronic, and in the context of memory,

doesn't actually need to take any steps.

Electronically a computer can jump to any location in memory

instantly in so-called constant time.

So just one step, that might take me several.

And so that's an advantage a computer has and it's just one of the reasons

why they are so much faster than us at solving so many problems.

But the key ingredient to laying out the data for a computer to solve

your problems quickly is that you need to put your data back-to-back-to-back.

Because a computer at the end of the day,

yes, stores only 0's and 1's, but those 0's and 1's are generally

treated in units of, say, eight--

8 bits per byte.

But those bytes, when storing numbers like this,

need those numbers to be back-to-back-to-back and not just

jumbled all over the place.

Because it needs to be the case that the computer is

allowed to do the simplest of arithmetic to figure out where to look.

Even I in my head am sort of doing a bit of math figuring out,

well where's the middle?

Even though among few doors you can pretty much eyeball it quickly.

But a computer's going to have to do a bit of arithmetic, so what

is that math?

Well if I have 1, 2, 3, 4, 5, 6, 7 doors initially,

and I want to find the middle one, I'm actually just going to do what?

7 divided by 2, which gives me 3 and 1/2-- that's

not an integer that's that useful for counting doors,

so let's just round it down to 3.

So 7 divided by 2 is 3.5 rounded down to 3 suggests

mathematically that the number of the door that's in the middle of my doors

should be that known as 3.

Now recall that a computer generally starts

counting at 0 because 0 bits represent 0 in decimal,

and so this is door 0, 1, 2, 3, 4, 5, 6.

So there's still seven doors, but the first is 0 and the last is called 6.

So if I'm looking for number 3, that's 0, 1, 2, 3.

And indeed, that's why I jumped to the middle of these doors,

because I went very specifically to location 3.

Now why did I jump to 42 next?

Of course, that was in the middle of the three remaining doors,

but how would a computer know mathematically where to go,

whereas we can just rather eyeball it here?

Well if you've got 3 doors divided by 2, that gives me, of course, 1.5--

let's round that down to 1.

So if we now re-number these doors, it's 0, 1, 2,

because these are the only three doors that exist, well door 1 is 0, 1--

the 42, and that's how a computer would know to jump right to 42.

Of course, with just one door left, it's pretty simple.

You'd needn't even do any of that math if there's just one,

and so we can immediately access that in constant time.

In other words, even though my human feet are taking a bit of energy

to get from one door to another, a computer has the leg-up, so to speak,

of getting to these doors even quicker, because all it has to do

is a little bit of division, maybe some rounding,

and then jump exactly to that position in memory.

And that is what we call constant time, but it presupposes, again,

that the data is laid out back-to-back-to-back so that every one

of these numbers is an equal distance away from every other.

Because otherwise if you were to do this math

and coming up with the numbers 3 or 1, you

have to be able to know where you're jumping in memory,

because that number 42 can't be down here, it has to be numerically in order

exactly where you expect.

And so in computer science and in programming is this kind of arrangement

where you have doors or really data back-to-back-to-back known

as what's called an array.

An array is a contiguous block of memory wherein values are stored

back-to-back-to-back-to-back-- from left to right conceptually,

although of course, direction has less meaning once you're inside

of a computer.

Now it is thanks to these arrays that we were able to search,

even something like a phone so quickly.

After all, you can imagine in the physical world,

a phone book isn't all that unlike an array,

albeit a more arcane version here, because its pages are indeed

back-to-back-to-back-to-back from left to right, which is wonderful.

And you'll recall when we searched a phone book,

we were already able to describe the efficiency via which

we were able to search it-- via each of those three algorithms.

One page at a time, two pages at a time, and then one-half

of the remaining problem at a time.

Well it turns out that there's a direct connection even

to the simplification of that same problem.

If I have n doors and I search them from left to right, that of course