Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
To help further your understanding of algorithms, this course is going to look at two categories: sorting algorithms and searching algorithms. You could argue these are the easiest kinds of algorithms to learn. But in learning how these algorithms are designed, we'll cover useful concepts like "recursion" and "divide and conquer" that are used in many other sorts of algorithms, and can even be used to create brand new ones.
You can learn more about Binary Search in our Introduction to Algorithms course.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
[MUSIC]
0:00
You may have heard that algorithms and
computer science are boring or
0:09
frustrating.
0:12
They certainly can be hard to figure out,
0:13
especially the way some
textbooks explain them.
0:15
But once you understand what's going on,
algorithms can seem fascinating,
0:18
clever, or even magical.
0:22
To help further your understanding
of algorithms, this course is
0:24
going to look at two categories, sorting
algorithms and searching algorithms.
0:27
You could argue that these are the easiest
kinds of algorithms to learn.
0:32
But in learning how these
algorithms are designed,
0:36
we'll cover useful concepts like recursion
and divide and conquer that are used in
0:38
many other sorts of algorithms, and could
even be used to create brand-new ones.
0:42
By the way, all the codes sample I'm going
to show in the videos will be in Python,
0:47
because it's a popular language
that's relatively easy to read.
0:51
But you don't need to know Python
to benefit from this course.
0:54
You can see the teachers notes for
each video.
0:57
For info on implementing these algorithms
in your own favorite language.
0:59
Our goal with this course is to give
you an overview of how sorting and
1:03
searching algorithms work.
1:07
But many algorithms have details that
can be handled in different ways.
1:08
Some of these details may
distract from the big picture, so
1:12
we've put them in
the teacher's notes instead.
1:15
You don’t need to worry about these when
completing the course for the first time.
1:17
But if you’re going back and
1:21
referring to it later, be sure to check
the teacher's notes for additional info.
1:22
Suppose we have a list of names, it’s
a pretty big list, 100,000 names long.
1:26
This list could be part of
an address book or social media app.
1:31
And we need to find the locations of
individual names within the list,
1:34
possibly to look up additional
data that's connected to the name.
1:38
Let's assume, there's no existing function
in our programming language to do this, or
1:41
that the existing function doesn't
suit our purpose in some way.
1:46
For an unsorted list,
1:49
our only option may be to use linear
search, also known as sequential search.
1:50
Linear search is covered in more
detail elsewhere on our site,
1:55
check the teacher's notes for
a link if you want more details.
1:58
You start at the first element,
2:02
you compare it to the value
you're searching for.
2:03
If it's a match, you return it,
if not, you go to the next element.
2:05
You compare that to your target.
2:10
If it's a match, you return it,
if not, you go to the next element, and
2:11
so on through the whole list.
2:15
The problem with this is that you have to
search the entire list every single time.
2:18
We're not doing anything to
narrow down the search each time.
2:23
We have to search all of it.
2:25
If you're searching a big list or
2:28
searching it repeatedly, this amount
of time can slow your whole lab down,
2:29
to the point that people may
not want to use it any more.
2:33
That's why it's much more common to use
a different algorithm for searching lists,
2:36
binary search.
2:41
Binary search is also covered in
more detail elsewhere on our site.
2:41
Check the teacher's notes for a link.
2:45
Binary search does narrow
the search down for us.
2:48
Specifically, it lets us get rid of half
the remaining items we need to search
2:50
through each time.
2:55
It does this by requiring that
the list of values be sorted.
2:56
It looks at the value in
the middle of the list.
3:01
If the value it finds is
greater than the target value,
3:04
it ignores all values after
the value it's looking at.
3:06
If the value it finds is
less than the target value,
3:09
it ignores all values before
the value it's looking at,.
3:12
Then it takes the set of
values that remain and
3:15
looks at the value in
the middle of that list.
3:17
Again, if the value it finds is
greater than the target value,
3:20
it ignores all values after
the value it's looking at.
3:23
If the value it finds is
less than the target value,
3:26
it ignores all values before
the value it's looking at.
3:28
But as mentioned,
3:32
binary search requires the list of values
you're searching through to be sorted.
3:33
If the list weren't sorted, you would
have no idea which half of the values
3:37
to ignore, because either half could
contain the value you're looking for.
3:41
You'd have no choice but
to use linear search.
3:45
So before we can use
binary search on a list,
3:48
we need to be able to sort that list.
3:50
We'll look at how to do that next.
3:52
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up