Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part class is designed to train students in the mathematical concepts and process of "Algorithmic Thinking", allowing them to build simpler, more efficient solutions to computational problems. In part 2 of this course, we will study advanced algorithmic techniques such as divide-and-conquer and dynamic programming. As the central part of the course, students will implement several algorithms in Python that incorporate these techniques and then use these algorithms to analyze two large real-world data sets. The main focus of these tasks is to understand interaction between the algorithms and the structure of the data sets being analyzed by these algorithms. Once students have completed this class, they will have both the mathematical and programming skills to analyze, design, and program solutions to a wide range of computational problems. While this class will use Python as its vehicle of choice to practice Algorithmic Thinking, the concepts that you will learn in this class transcend any particular programming language.
Efficiency of binary search
Loading...
From the course by Rice University
Algorithmic Thinking (Part 2)
150 ratings
From the lesson
Module 3 - Core Materials
Sorting, searching, big-O notation, the Master Theorem
Meet the Instructors
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Okay, so now we have done binary search, and we have seen how it works.
And it takes the list, divided in two halves, decides on which half to go to.
It comes here and divide and decide which half, and so on.
Until it gets to an item, to a list of one item and
then checks, is that the item I'm looking for?
If not, it just returns minus 1.
If yes, it returns the, the index of that item and done.
So what is the running time of this algorithm, okay?
It is a recursive.
We will have a recursive implementation of it.
It is divide and conquer.
And let's think about it the similar way that we thought about about So
I'm looking at the running time of this T of n.
And I'm saying, how long does binary source take on a list of size n?
Okay.
So what did, what did binary search do?
It divided the list into two halves.
Each of size n over 2.
Remember that this was.
This number here is the number of, of sub problems.
And n over 2 is the size of each sub problem.
It divided into two halves.
How many of them did we solve?
So when I call binary search again, I am not calling it on this and this.
Actually, when I divide it into two halves, as I said this we kill this
branch, because I know I'm not, I don't the element is not going to be here.
So I don't solve in merger sort it was 2 times t over n over 2,
because I know that to solve the left half, I need to solve the right half.
In binary search, once you decide it's not in the left half you ignore it.
Therefore, and you just go on the right half.
Therefore it is 1 times t of n over 2.
So we, we divide it into 2 sub problems, or 2 less each of size n over 2.
We solve one of them, we solve one of them.
And then, see, how long does it take to do the merge?
Merge in fact, it's why we don't do any merge, and it is O of 1.
Okay?
It is O of 1.
For the base case T of 1 is O of 1 as well, right?
In the case of this one last you are just doing the comparison.
So, this again we go back to the issue of we have, we have
a recurrence and the recurrence, is of the right form for the master theorem.
Again remember the master theorem applies to recurrence of the form T of n
equal a of T of n divided by b plus f of n.
Where f of n is O of n to the d, right?
So here this was the kind of recurrence that it applies to.
What is a?
It's 1.
What is b?
It's 2.
What is d?
O of 1 is 0 of n to the 0.
So d is 0, right?
So for binary search, a is 1, b is 2, d is 0.
Remember, for merge sort, it was, a is 2, b is 2, d is 1, okay?
So binary search has a little bit of a difference with the, with the merge sort.
Remember, for the master theorem, the first thing to check is.
How does a compare to b to the d, a is 1, b is 2, and d is 0.
2 to the 0 is 1, 1 equal.
So we have a equal b to the d.
Remember the master theorem says that if a equals b to the d, then T of n
equals all of n to the d log n.
In our case, d is 0.
So it's of n to the 0 log n.
So the running time of my, of binary search is actually log n.
And, it should make sense because, this, algorithm is going to divide,
look at this half, divide, look at this half, divide, look at this half.
So, really, the amount, the amount of work that it's doing is best than this,
than this, than this, so I'm going one call, one call, one call, one call.
So, it's basically the height of this tree, going from here to here, so
it's just one path.
That is going to take.
What is the height of this tree?
If you think about it carefully, because I take this divided it into two.
This into two.
This into two.
Where do I stop?
If this had n, you will notice that you will have to
stop after log of n of course it's base 2.
So, the height of this tree is going to be all of log n.
And this is why, this algorithm is actually going to take log n.
So this is the intuitive explanation,
that the height that it's going to take is log n.
And the same thing here, the master theorem, without thinking too much,
it will have given me exactly the same thing, O of log n.
So binary search is O of log n, linear sear, search is O of, of of n.
Again, binary search is O of log n.
And linear search, of n.
So, does this mean that, every time I have search,
I always run binary search, because log n is better?
The answer is no because, remember that there's a big
assumption about binary search, that the list has to be sorted.
If it is not sorted, this is not going to work.
If it is not sorted, this will work.
This works on anything.
Whether it is sorted or not sorted, this will work, okay?
And the worst case is we will take O of n, regardless of it is sorted or not.
This one is going to take in the worst case of login.
So, when you have a list and an item, and
you're searching for them, Yyu do a binary search or a linear search.
[COUGH] If it is not if it's not sorted,
you can either do O a linear search or you can sort and do binary search, okay?
So.
I can do linear search.
I can do linear search, which will
take O of n or, I can do sort, first,
and then I can do binary search.
But, this is going to take, we have seen it already,
n log n, plus O of log n, and this is of course O of n log n.
So it doesn't make any sense to sort, and do binary search.
Just do linear search, and you are going to get the O of n.
So would we ever sort, and do binary search over this?
The answer is no.
If all you need to do is just one search operation, if,
if all you care about is just one-time search, you should do this.
If all you care about is twice, three times, four times,
seven times, a small number of searches, do this.
But, imagine what would happen if you have a list with, with millions of items, and
your search operation is done millions of times.
Then it is worth putting the effort into searching first, and
then start doing all the other search queries in log n, okay?
So, this is a very important algorithmic principle here.
That sometimes, it is worth pre-processing the data,
before we start doing the actual operations we're interested in.
The pre-processing here was sorting, so that I can do the search efficiently.
It is, this is worth it when n log n is not going to be the main factor.
N log n is not the main factor.
It is when the number of operations here, actually overwhelms this.
So I will always have n log n for the sorting, plus k
times log n, where k is the number of search queries that I will be executing.
If k is much larger than n, this is worth it.
If k is too small this is not worth it.
Okay.
So this here,
now that we have seen sort, you can start using sort as a pre-processing technique,
pre-process the data and do the other operations much, much faster.
This belongs in some sense to the category of transform and conquer.
This kind of approach in the sense that I wanted to do a search on a list,
I transform the instance of the problem by sorting it,
and then I did my actual solution to the problem, okay.
So keep in mind that sorting while it is about getting a sorted list of items.
Sometimes we, it is a very powerful technique for pre-processing the data, so
that subsequent operations, whether they are searching or comparison, and
so on, can be done very efficiently.
Okay?
There are many operations, that if you do them on an unsorted list are going to be
very unefficient, inefficient.
And these operations, once you have preprocessed the data so
that it is sorted, they become efficient all of a sudden.
So it's very important to keep in mind that, if you are doing just one search
operation, or five, or 100, or, or 1,000, it is not worth going through this.
Do linear search.
If the number of queries is, is, growing all the time, and
it is a very large number.
It is worth pre processing the data so
that every time you do the query, it is taken a short amount of time, okay.
So in this set of lectures we have seen divide and conquer technique, for
merge sort, for binary source, how we divide a big problem into sub problems.
Then solve each one of them, and then merge the results.
Remember that there are three steps.
We have seen that,
the natural implementation of these algorithms is recursive, where you
call the functions multiple times on the, in the instances of the sub problems.
We saw that these recursive algorithms naturally give rise,
to formulas that we call recurrences for the running time of the algorithms.
We have seen how recurrences of this specific form can be solved using
the master theorem, to give us an explicit function that we understand.
I want to emphasize once more.
Master theorem is not a framework for solving all recurrences.
The recurrences have to be of a specific form, satisfies that the conditions for
it to apply.
And the last thing we saw is that using this technique of sorting,
I can use it as a pre-pocessing to pre-process lists of, of numbers,
of strings and so on so that later when I apply other operations like searching or
comparing the two closes elements and so on.
I can, I can get that operation done in much faster amount of time.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
