**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.

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 up