This course will be retired on June 1, 2025.
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
Lists can be searched much faster using BinarySearch once they're sorted.
System.Collections.Generic.List
For more about delegates, see stage 2 of the Querying With LINQ 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
Earlier, we saw how to find the index of
an item using the list index of method.
0:00
If we look at the documentation for the
list collection, we'll see that the list
0:06
class contains other methods for
finding items in the list.
0:10
There are many methods here
that start with the word find.
0:13
These all take as a parameter a special
type of object called a predicate.
0:21
A predicate is yet
0:28
another type of delegate,
if you remember from the previous video,
0:29
a delegate is a function that can be
passed around like any other object.
0:33
Predicate delegates take a parameter and
return a boolean.
0:36
In this case, the predicate returns
true if the object passed to them
0:40
is the item that's being searched for.
0:45
We'll learn more about predicates
when we learn about delegates and
0:47
functional programming in a later course.
0:50
Internally, all of these fine methods
search through the list one by one.
0:52
Like the index of method, these
methods along with the index of method
0:58
are sufficiently fast when
searching small list of items or
1:02
if only doing a few searches.
1:06
However, we can greatly increase how
quickly items can be found in the list
1:08
if the list is sorted.
1:13
If our list is already sorted, we can
use the binary search methods up here.
1:15
The binary search methods take
advantage of the fact that the list
1:22
is already sorted.
1:26
In fact, if we call BinarySearch
on a list that isn't sorted,
1:28
it's unlikely to even find
the item we're searching for.
1:32
It's named BinarySearch because it uses
the BinarySearch algorithm to search
1:35
through the list.
1:39
If it takes the index of or
1:40
find methods 1000th of a second
to search the entire list.
1:42
The BinarySearch method can search
the list in one 100th of the time.
1:47
The performance of
the BinarySearch algorithm
1:51
improves logarithmically as
the number of items increases.
1:54
So, the more items there are in the list,
1:58
the faster the binary search method will
run relative to the other search methods.
2:01
So, it only takes twice as much time
to search a list of a million items
2:06
as it does to search
a list of 1,000 items.
2:11
Now, that's pretty neat.
2:14
I've included more information
about the BinarySearch algorithm
2:15
in the teacher's notes.
2:18
Just like the sort method,
2:20
the BinarySearch method also relies on the
IComparable or the IComparer interfaces.
2:21
The items in the list must either
implement the IComparable interface or
2:27
an object of IComparer must be
passed to the BinarySearch method.
2:31
Just like the index Of() method,
2:35
the binary search method
returns the index of the item.
2:37
If the item isn't in the list,
it returns a negative number.
2:41
When calling indexOf,
this negative number is always -1.
2:45
With BinarySearch, however,
the negative number returned
2:49
tells us where the item
should go in the sorted list.
2:53
Let's say we want to add a new
student to our list of students.
2:57
But we wanna keep the list sorted.
3:00
So, right here after we've sort of the
list, in main, let's create a new student.
3:03
So, I'll say Student
3:09
newStudent = new Student and
3:14
we'll give it a name of Joe and
3:19
Joe will be in grade level 2.
3:25
Now, let's search the list to see
if second grade Joe is in it.
3:31
So, say int index equals
3:37
students.BinarySearch and
we'll pass in the new student.
3:40
If Joe is in the list the index
here will be a positive integer.
3:50
If he's not in the list, we'll add him.
3:55
So, if index is less than 0.
3:57
We'll insert him at the proper location,
so we'll say students.insert.
4:06
Now, here we need to specify the index
where we want to put the new student.
4:16
It isn't as simple as just
turning that negative number
4:21
into a positive number to get the index.
4:24
Instead, the negative number
returned by BinarySearch is actually
4:27
the negative index -1.
4:32
This resolves the issue where
the item should be a index 0.
4:34
if BinarySearch returned 0,
4:38
it would mean that the item is
already in the list at index o.
4:40
So, instead BinarySearch returns index and
then subtract ones from it.
4:45
So, if Joe should be at index one in
the list BinarySearch will return -2.
4:50
So, to get back to -1,
we can turn the -2 into +2 and subtract 1.
4:56
So say, just take the negative index and
5:03
subtract 1 and
we'll insert the new student there.
5:06
This here is also known as taking
the bit wise complement of an integer.
5:14
And there's an operator to do just that.
5:20
We can change this to ~index.
5:22
This has the same effect as negating
the index and subtracting 1.
5:29
This tilde symbol is one
of many bit wise operators.
5:34
It's all right if you haven't
used bit wise operators before.
5:38
They aren't something that most
developers work with very often, so
5:41
I'm not going to go into much more
detail about them in this course.
5:44
That's a topic for another course.
5:47
If you'd like to learn more about them,
check the teachers notes for
5:49
more information.
5:52
Now, let's compile the C if
we've introduced any errors.
5:54
Now, let's run to see the results
of adding Joe to our list.
5:58
As you can see we were able
to add a new student and
6:04
we maintained the sorted
order of the list.
6:07
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