Hello World!
I'm talking about searching.
I have a list of names here,
and they are not in any particular order.
I have them from to 1 to 20,
So the size of this list is 20.
We usually refer to that as n.
In an array these would be from 0 to 19.
Since they're not sorted
and I need to find a name in the list,
my only choice is to use a loop and
check for the name here and here, and so on,
until either find it
or I've looked at the last element and it's not there.
In the worst-case scenario which is
what Big O notation measures,
worst-case scenario would be n.
It would take me 20 guesses
to find that the name I'm looking for isn't there.
On average, it would be about 10.
Sometimes I would find it up here, sometimes down here.
But on average, if  the name is there,
it would take me n divided by 2 guesses
to find it.
Let's see how a binary search works.
In a binary search, the names absolutely have to be
in alphabetical order, so let's just sort them.
And now,  if the name is there,
it  is going to be somewhere
between one and a max value
of 20.
And with a binary search we start in the middle.
so my first guess is going to be the average
of min and max, which is 10.
So,  let's have a name were looking for here.
Let's do one that is actually on the list, like Ryan.
OK.  So I look at position 10
and I've see Lin.
Ryan comes after Lynn alphabetically.
So what I do is,
because Ryan comes after Lin,
the minimum position
where Ryan could be, would be in position 11.
so I've change min to 11.
That's  actually guess minus,  guess +1.
and so now I'm looking in position 15.
and I see Ron , and Ryan comes after Ron.
so the minimum is 16.
Or guess+1.
My next gas is 18.
Ted.
Ryan comes before Ted alphabetically.
Since he comes before Ted, the maximum
position the name could be in
and that is guess -1.
and so we change this to 17.
guess is 16.
And there's Ryan.
And he's in position 16.
We probably have some other information over here,
in a parallel  array that we're looking up.
But there's our search.
Let's go back to a new search.
and put  1 and 20 as min and max again.
and this time, let's look for somebody
who isn't there, let's search for Carl.
And my first guess is 10.
and Carl comes before Lin alphabetically.
so the maximum it could be is guess -1
and we change that to 9.
and my next guess is position 5.
and Carl comes before Deb, alphabetically.
So I'm going to change my max
to guess -1 again,
making that 4.
and my next guest is position 2, Amy.
Carl comes after Amy,
so we change min to guess plus 1,  is 3.
And I'm now looking at Bill.
Carl comes after Bill.
so I change max
to guess -1 which is two.
and at this point they crossed over:
min is greater than max
and I know that name isn't there.
That's what we're looking for.
We're going to keep changing either min or max,
making a new guess
until either we find it
or men is greater than max.
at  that point we know it's not found.
And that's it.