This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.
Binary Search
Loading...
Del curso dictado por Rice University
Principles of Computing (Part 2)
235 calificaciones
De la lección
Recursion
This week, we will explain the importance of recursion.
Conoce a los instructores
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[MUSIC]
So, today I'm going to illustrate the notion of divide and conquer
algorithms, and recursive implementation, as
a mechanism for reasoning about problems.
And I'm going to use the problem, a very common problem,
that's used in textbooks, algorithms textbooks, it's called binary search.
Or in general the search problems, and the problem is defined as follows.
I'm giving a list of numbers.
Let's think about it as a list of numbers.
And the list is sorted, let's say in ascending order.
So I have 5, 7, 9, 15, 27, 35, 100.
So I have this list as an input, some, someone gave me this list.
And in addition, they're giving me some element k.
And that k is, for example, 35.
And the question that we want to answer is that, is k in the list L?
Okay?
So, the first the first approach that one would think
about is, okay, I can look at the list, scan
the list from left to right, I see okay, 35
is here, so I can say, yes it is there, okay?
So I'm going to look at the version the problem where, I will say,
yes, or true, the element is in the list, or no, or false.
If the element is not in the best.
Okay?
So the first approach to some problem like this or
the native approach, is that just scan the list again.
And if I want to write it in, in not real code, but
in something, some hybrid between English and real code, which we call pseudocode.
And an approach like this.
So suppose I have, I have the left starting at
position zero, and all the way to position n minus 1.
So it has n elements, and [INAUDIBLE] zero to n minus 1.
So, one way to, to, to approach this problem, or
to solve it, I can say for I equals 0, to n minus 1.
If L the ith element, if it is equal
to this K that I'm interested in, return true.
[SOUND] Else, here, if I, if I have gone through all the
elements and haven't found it, I can return false.
Okay?
So this is an approach actually for solving this problem.
It is taking as input this list L, and
element K, and it's going to return true if
K is found at some index within this list,
or it's going to return false, if it's not there.
This approach here, because I'm scanning the entire
list, this is known as linear, search, okay?
Now, you have heard about growth of functions and how, how
the running time of algorithms changes as we increase input size.
So if I look at the input size here as the size of this list, which is n.
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.
If it's not this, which means everything is fine.
I passed the left and right boundaries legitimate values.
Now I need to find the midpoint there, so I will
call that M or mid, let's say, and mid I'm going to set
it to, I can use left arrow, also in this notation to
set a value or to assign a value to this variable mid.
I'm going to say it's L plus R divided by 2, okay?
Now, just a small detail here, what if again, L is 0 and R
is, is 6, so 0 plus 6 is 6, divided by 6 is 3.
What if it was 0 and 7?
0 plus 7 is 7, divided by 2 is 3.5.
But 3.5 is not the index in the array, so what do I do about that?
Here you have to make a decision.
You either round it down to 3, or you round it up to 4.
Okay, and you have to be consistent about that.
So here I'm going to use this notation.
Which we call the floor, which will rounded it down.
So if this L plus R is 7, 7 divided by 2 is 3.5, the floor of that is 3.
Okay, so this value of mid is going to be 3.
Then once we have, I found this mid point, I ask
a simple question, is K equal to the value at the midpoint?
[SOUND] Is it equal to that?
If that, if that's the case, we have none.
I return true.
If it's not, again, now I need to see is, is
the element smaller than the value at the midpoint or bigger?
If, the element is smaller than the midpoint.
Then,
I have to repeat exactly the same process, which is binary search, on the left half.
So if this is the midpoint,
I need now to repeat it on this, but what are the boundaries of this?
L doesn't change.
We still have L here.
And this is mid minus 1.
Right?
So now I have to repeat binary search.
[SOUND] On the same list, but now I take the boundaries to be a L and
mid, minus 1, and I'm still looking for the same value.
Else, if K is greater than the midpoi, the value
at the midpoint, then else, I can do binary search
[SOUND] L, but now I need to do it on this part here.
So it's from mid plus 1, right?
2R, so I need to do it, so them the, the left boundary is the entry
next to the midpoint, which is mid, at mid plus 1, all the way to R.
And I'm looking for K, okay?
So this is, this is the algorithm that will do this binary search on this list.
Notice that I am calling the same function.
Okay?
Which is a recursive call.
The only thing that changes is what are the
boundaries, while I am looking at that element, right?
So, am I looking at the left half or the right half?
And when I repeat the process, when I go to the left half, I go either
to the left of that left have or the right of the, that ri left half.
But I repeat the same process over and over, and this is an
example of binary search, and this is how we would write it recursively, okay?
I am not going to go through mathematical details here.
But, as an exercise, it's a bit of challenging
exercise based on the materials we have covered so far,
you can see that the running time, whereas this
is linear, if you double the the running ti, if
you double the size of the input, you double
the running time, here you will see that if you
take n, for example, and you go from n equal
8, to n equals 16, in terms of the input.
So if you start with a list that has eight elements, verses a list
of 16 elements, you will find that here, you will be doing roughly about
three operations, if you do this, you are going to go to four operations,
if you go to 32, so I am doubling, I'm going to go to five.
So I'm doubling the input, but whenever, the input size, whenever I double
the input size, the running time is increasing only by one operation, oaky?
And this growth is actually log of n, where
when, when n is the size of the list.
So, this algorithm, this binary search, is much
better than linear search, in terms of running time.
Instead of doing linear time, we are doing it
logarithmic time, which grows much slower than linear time.
But, I want to remind you once again, that whereas
linear search works on any list, for finding an
element, binary search, a very important precondition for this
to work, is that the list has to be sorted.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
