Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic 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.

0:00
Earlier, we saw how to find the index of an item using the list index of method.

0:06
If we look at the documentation for the list collection, we'll see that the list

0:10
class contains other methods for finding items in the list.

0:13
There are many methods here that start with the word find.

0:21
These all take as a parameter a special type of object called a predicate.

0:28
A predicate is yet

0:29
another type of delegate, if you remember from the previous video,

0:33
a delegate is a function that can be passed around like any other object.

0:36
Predicate delegates take a parameter and return a boolean.

0:40
In this case, the predicate returns true if the object passed to them

0:45
is the item that's being searched for.

0:47
We'll learn more about predicates when we learn about delegates and

0:50
functional programming in a later course.

0:52
Internally, all of these fine methods search through the list one by one.

0:58
Like the index of method, these methods along with the index of method

1:02
are sufficiently fast when searching small list of items or

1:06
if only doing a few searches.

1:08
However, we can greatly increase how quickly items can be found in the list

1:13
if the list is sorted.

1:15
If our list is already sorted, we can use the binary search methods up here.

1:22
The binary search methods take advantage of the fact that the list

1:26
is already sorted.

1:28
In fact, if we call BinarySearch on a list that isn't sorted,

1:32
it's unlikely to even find the item we're searching for.

1:35
It's named BinarySearch because it uses the BinarySearch algorithm to search

1:39
through the list.

1:40
If it takes the index of or

1:42
find methods 1000th of a second to search the entire list.

1:47
The BinarySearch method can search the list in one 100th of the time.

1:51
The performance of the BinarySearch algorithm

1:54
improves logarithmically as the number of items increases.

1:58
So, the more items there are in the list,

2:01
the faster the binary search method will run relative to the other search methods.

2:06
So, it only takes twice as much time to search a list of a million items

2:11
as it does to search a list of 1,000 items.

2:14
Now, that's pretty neat.

2:15
I've included more information about the BinarySearch algorithm

2:18
in the teacher's notes.

2:20
Just like the sort method,

2:21
the BinarySearch method also relies on the IComparable or the IComparer interfaces.

2:27
The items in the list must either implement the IComparable interface or

2:31
an object of IComparer must be passed to the BinarySearch method.

2:35
Just like the index Of() method,

2:37
the binary search method returns the index of the item.

2:41
If the item isn't in the list, it returns a negative number.

2:45
When calling indexOf, this negative number is always 1.

2:49
With BinarySearch, however, the negative number returned

2:53
tells us where the item should go in the sorted list.

2:57
Let's say we want to add a new student to our list of students.

3:00
But we wanna keep the list sorted.

3:03
So, right here after we've sort of the list, in main, let's create a new student.

3:09
So, I'll say Student

3:14
newStudent = new Student and

3:19
we'll give it a name of Joe and

3:25
Joe will be in grade level 2.

3:31
Now, let's search the list to see if second grade Joe is in it.

3:37
So, say int index equals

3:40
students.BinarySearch and we'll pass in the new student.

3:50
If Joe is in the list the index here will be a positive integer.

3:55
If he's not in the list, we'll add him.

3:57
So, if index is less than 0.

4:06
We'll insert him at the proper location, so we'll say students.insert.

4:16
Now, here we need to specify the index where we want to put the new student.

4:21
It isn't as simple as just turning that negative number

4:24
into a positive number to get the index.

4:27
Instead, the negative number returned by BinarySearch is actually

4:32
the negative index 1.

4:34
This resolves the issue where the item should be a index 0.

4:38
if BinarySearch returned 0,

4:40
it would mean that the item is already in the list at index o.

4:45
So, instead BinarySearch returns index and then subtract ones from it.

4:50
So, if Joe should be at index one in the list BinarySearch will return 2.

4:56
So, to get back to 1, we can turn the 2 into +2 and subtract 1.

5:03
So say, just take the negative index and

5:06
subtract 1 and we'll insert the new student there.

5:14
This here is also known as taking the bit wise complement of an integer.

5:20
And there's an operator to do just that.

5:22
We can change this to ~index.

5:29
This has the same effect as negating the index and subtracting 1.

5:34
This tilde symbol is one of many bit wise operators.

5:38
It's all right if you haven't used bit wise operators before.

5:41
They aren't something that most developers work with very often, so

5:44
I'm not going to go into much more detail about them in this course.

5:47
That's a topic for another course.

5:49
If you'd like to learn more about them, check the teachers notes for

5:52
more information.

5:54
Now, let's compile the C if we've introduced any errors.

5:58
Now, let's run to see the results of adding Joe to our list.

6:04
As you can see we were able to add a new student and

6:07
we maintained the sorted order of the list.
You need to sign up for Treehouse in order to download course files.
Sign up