And I look at, and I look at, and as it increases
from 2, let's say, to 4 to 8 to 16, and so on.
You will notice that if I double the size of
the list, the running time, roughly, is going to double, right?
So, I'm going to be looking at twice the number of elements.
If I triple it, it's gon, the running time is going to triple, because
I'm going to be looking at three times the number of elements, and so on.
Now, this algorithm is fine.
Linear running time is good, is fine, no problem with that.
But one of the things that this algorithm
is discarding, or not taking into consideration, is
that I said the list is already sorted, okay, so it is sorted in ascending order.
Can we use that fact, to make our algorithm more efficient, okay?
And the answer is yes.
Think about it for, for a second,
just forget about, let's, and think about dictionary.
When you are looking for a word
in dictionary, the dictionary is sorted, right?
I mean, it's sorted alphabetically.
Now, when you look up for a, when you look up a word in the dictionary, you
don't go from the first page and, the second
page and then the third page looking for that.
No, we usually open the dictionary to the middle, for example.
Roughly the middle.
And then we say okay, what is the word that we are looking for?
Suppose the word starts with the letter S, and
we opened the dictionary and we are at letter M.
We know that S comes after M, so we go to the right, of that midpoint.
And we repeat this process.
Exactly the same idea is going to be applied here.
I am looking for this element 35.
All right?
So, since that list is, is, is sorted,
I'll say, I'm not going to scan it linearly, I
am going to go to the middle point of this list, which is this point here, okay?
So, I'm going to, to go this point, and I'm going to ask, is 35 positioned
there, or is the element 35 found at that midpoint of the list?
If the, if 35 is there, I am done, I found it already in one operation.
I went to that midpoint, and found it there, I am done, I return true.
If it's not there, I have one of two choices now.
Either 35 or that element I'm looking for, is smaller than the value at the midpoint.
Or it is bigger than the value at the midpoint.
If it is smaller, so suppose I am looking for element eight,
If I'm looking for element eight, of course 15 does not equal eight.
Because the list is sorted in ascending order, I
know now I need to see if eight is to
the left of this number, right, because it's smaller
than it, and the list is sorted in ascending order.
I am looking for the 35, I go to the midpoint, its not there.
I know for sure, that if 35 is in the
list, it has to be to the right of this point.
If its not to the right, if its in the list and not to the
right, then the list is not sorted
in ascending order, so that violates my assumption.
So, if 35 is to the right, what do I do?
Okay, if it's, I want to find if it's to the right of 15.
Now, I am going to repeat exactly the same process.
I am now going to look at this half of the list.
I'm going to go to the midpoint of that half, I
am going to check if 35 is there, if it's not there.
And smaller than the value, I'm going to go to the left of that midpoint.
If it's bigger, I'm going to go to the right of that midpoint.
So, since I am doing exactly the same process, and I will repeat
it over and over and over, this is exactly where we use recursive implementations.
This is a divide and conquer algorithm, because I am dividing
the list at every point, I am dividing it into two halves.
And then I'm concurring the problem by going either
to the left half or to the right half.
Whenever I go to the left or to
the right, I'm repeating exactly the same process, right?
And this is why we use or invoke recursive implementation here.
Because I don't have to keep repeating the details of that process.
I say, here is a black box that going to, implement some, some some
procedure, just keep applying that black box to the left or to the
right, depending on answering that simple question, which is is the element smaller
than the one, the midpoint, or greater than the element at the midpoint?
So, how would I write that algorithm?
Again if I want to, if I want to illustrate
35 completely with this, I say okay, here's
the midpoint, 35 is not here, it is bigger than 15, so I look at this.
So now, I repeat the process on this.
What is the midpoint of that?
It has three elements, this is the midpoint now.
Right?
When I go here, I say if 35 equal to
this, I found it, I return true, and I'm done, right?
So, you keep doing this process.
This is a procedure, or this is
a description of the algorithm for linear search.
How would I do a binary search, how would, how would I implement this?
Again, using this, the, this kind of, of coding
style, I will define the, the function binary search.
[SOUND] That's going to take as input this this,
this list or array that's sorted in ascending order, L.
It's going to take, in addition, two indices here, and I'm going to
call them L and R for left and right, which are giving me
the boundaries, so when I call the function in the beginning, they are
going to be 0 and n minus 1, if the list has n element.
And I have that element K that I'm looking for, okay?
Again, this is the list that I'm trying to see if the element is in.
This is the element I'm trying to find if it's there.
L and R and the left and right boundaries.
So when we start with this list.
[SOUND] So if I copy this 5, 7, 9,
15, 27, 35, 100.
So L, to begin with, L equal 0, and R equals 6, okay?
So, L equals 0 and, and, and R equals 6.
I'm going to be looking for that, and when
I call the function in the beginning, I will
be doing binary search [SOUND] on this L, from
position 0 to position 6 of that element 35.
This is how I'm going to call this, okay?
So what are the details of this function?
As a sanity check in the beginning, L is the left and R
is the right, I want L to be at most equal R, right?
So I cannot, I'm not going to accept that L is greater than R.
So, as a sanity check first, if we say if L is greater than R.
If you pass this, return false.
[SOUND] Okay?
The element is not there.