1
00:00:00,540 --> 00:00:06,500
Earlier, we saw how to find the index of
an item using the list index of method.

2
00:00:06,500 --> 00:00:10,620
If we look at the documentation for the
list collection, we'll see that the list

3
00:00:10,620 --> 00:00:13,940
class contains other methods for
finding items in the list.

4
00:00:13,940 --> 00:00:16,948
There are many methods here
that start with the word find.

5
00:00:21,838 --> 00:00:28,070
These all take as a parameter a special
type of object called a predicate.

6
00:00:28,070 --> 00:00:29,440
A predicate is yet

7
00:00:29,440 --> 00:00:33,060
another type of delegate,
if you remember from the previous video,

8
00:00:33,060 --> 00:00:36,970
a delegate is a function that can be
passed around like any other object.

9
00:00:36,970 --> 00:00:40,830
Predicate delegates take a parameter and
return a boolean.

10
00:00:40,830 --> 00:00:45,210
In this case, the predicate returns
true if the object passed to them

11
00:00:45,210 --> 00:00:47,290
is the item that's being searched for.

12
00:00:47,290 --> 00:00:50,440
We'll learn more about predicates
when we learn about delegates and

13
00:00:50,440 --> 00:00:52,940
functional programming in a later course.

14
00:00:52,940 --> 00:00:58,020
Internally, all of these fine methods
search through the list one by one.

15
00:00:58,020 --> 00:01:02,650
Like the index of method, these
methods along with the index of method

16
00:01:02,650 --> 00:01:06,430
are sufficiently fast when
searching small list of items or

17
00:01:06,430 --> 00:01:08,410
if only doing a few searches.

18
00:01:08,410 --> 00:01:13,080
However, we can greatly increase how
quickly items can be found in the list

19
00:01:13,080 --> 00:01:14,180
if the list is sorted.

20
00:01:15,280 --> 00:01:20,110
If our list is already sorted, we can
use the binary search methods up here.

21
00:01:22,770 --> 00:01:26,510
The binary search methods take
advantage of the fact that the list

22
00:01:26,510 --> 00:01:28,100
is already sorted.

23
00:01:28,100 --> 00:01:32,220
In fact, if we call BinarySearch
on a list that isn't sorted,

24
00:01:32,220 --> 00:01:35,250
it's unlikely to even find
the item we're searching for.

25
00:01:35,250 --> 00:01:39,411
It's named BinarySearch because it uses
the BinarySearch algorithm to search

26
00:01:39,411 --> 00:01:40,830
through the list.

27
00:01:40,830 --> 00:01:42,780
If it takes the index of or

28
00:01:42,780 --> 00:01:47,212
find methods 1000th of a second
to search the entire list.

29
00:01:47,212 --> 00:01:51,620
The BinarySearch method can search
the list in one 100th of the time.

30
00:01:51,620 --> 00:01:54,170
The performance of
the BinarySearch algorithm

31
00:01:54,170 --> 00:01:58,410
improves logarithmically as
the number of items increases.

32
00:01:58,410 --> 00:02:01,220
So, the more items there are in the list,

33
00:02:01,220 --> 00:02:06,020
the faster the binary search method will
run relative to the other search methods.

34
00:02:06,020 --> 00:02:11,010
So, it only takes twice as much time
to search a list of a million items

35
00:02:11,010 --> 00:02:13,170
as it does to search
a list of 1,000 items.

36
00:02:14,190 --> 00:02:15,640
Now, that's pretty neat.

37
00:02:15,640 --> 00:02:18,480
I've included more information
about the BinarySearch algorithm

38
00:02:18,480 --> 00:02:20,000
in the teacher's notes.

39
00:02:20,000 --> 00:02:21,754
Just like the sort method,

40
00:02:21,754 --> 00:02:27,930
the BinarySearch method also relies on the
IComparable or the IComparer interfaces.

41
00:02:27,930 --> 00:02:31,840
The items in the list must either
implement the IComparable interface or

42
00:02:31,840 --> 00:02:35,920
an object of IComparer must be
passed to the BinarySearch method.

43
00:02:35,920 --> 00:02:37,960
Just like the index Of() method,

44
00:02:37,960 --> 00:02:41,520
the binary search method
returns the index of the item.

45
00:02:41,520 --> 00:02:45,350
If the item isn't in the list,
it returns a negative number.

46
00:02:45,350 --> 00:02:49,402
When calling indexOf,
this negative number is always -1.

47
00:02:49,402 --> 00:02:53,590
With BinarySearch, however,
the negative number returned

48
00:02:53,590 --> 00:02:57,070
tells us where the item
should go in the sorted list.

49
00:02:57,070 --> 00:03:00,820
Let's say we want to add a new
student to our list of students.

50
00:03:00,820 --> 00:03:02,240
But we wanna keep the list sorted.

51
00:03:03,380 --> 00:03:09,623
So, right here after we've sort of the
list, in main, let's create a new student.

52
00:03:09,623 --> 00:03:14,031
So, I'll say Student

53
00:03:14,031 --> 00:03:19,831
newStudent = new Student and

54
00:03:19,831 --> 00:03:25,631
we'll give it a name of Joe and

55
00:03:25,631 --> 00:03:31,440
Joe will be in grade level 2.

56
00:03:31,440 --> 00:03:37,190
Now, let's search the list to see
if second grade Joe is in it.

57
00:03:37,190 --> 00:03:40,329
So, say int index equals

58
00:03:40,329 --> 00:03:47,380
students.BinarySearch and
we'll pass in the new student.

59
00:03:50,750 --> 00:03:55,410
If Joe is in the list the index
here will be a positive integer.

60
00:03:55,410 --> 00:03:57,640
If he's not in the list, we'll add him.

61
00:03:57,640 --> 00:04:02,563
So, if index is less than 0.

62
00:04:06,211 --> 00:04:12,477
We'll insert him at the proper location,
so we'll say students.insert.

63
00:04:16,586 --> 00:04:21,490
Now, here we need to specify the index
where we want to put the new student.

64
00:04:21,490 --> 00:04:24,940
It isn't as simple as just
turning that negative number

65
00:04:24,940 --> 00:04:27,700
into a positive number to get the index.

66
00:04:27,700 --> 00:04:32,470
Instead, the negative number
returned by BinarySearch is actually

67
00:04:32,470 --> 00:04:34,090
the negative index -1.

68
00:04:34,090 --> 00:04:38,800
This resolves the issue where
the item should be a index 0.

69
00:04:38,800 --> 00:04:40,820
if BinarySearch returned 0,

70
00:04:40,820 --> 00:04:45,290
it would mean that the item is
already in the list at index o.

71
00:04:45,290 --> 00:04:50,740
So, instead BinarySearch returns index and
then subtract ones from it.

72
00:04:50,740 --> 00:04:56,980
So, if Joe should be at index one in
the list BinarySearch will return -2.

73
00:04:56,980 --> 00:05:02,430
So, to get back to -1,
we can turn the -2 into +2 and subtract 1.

74
00:05:03,430 --> 00:05:06,702
So say, just take the negative index and

75
00:05:06,702 --> 00:05:11,680
subtract 1 and
we'll insert the new student there.

76
00:05:14,600 --> 00:05:20,070
This here is also known as taking
the bit wise complement of an integer.

77
00:05:20,070 --> 00:05:21,800
And there's an operator to do just that.

78
00:05:22,830 --> 00:05:25,894
We can change this to ~index.

79
00:05:29,923 --> 00:05:34,320
This has the same effect as negating
the index and subtracting 1.

80
00:05:34,320 --> 00:05:38,310
This tilde symbol is one
of many bit wise operators.

81
00:05:38,310 --> 00:05:41,340
It's all right if you haven't
used bit wise operators before.

82
00:05:41,340 --> 00:05:44,580
They aren't something that most
developers work with very often, so

83
00:05:44,580 --> 00:05:47,920
I'm not going to go into much more
detail about them in this course.

84
00:05:47,920 --> 00:05:49,940
That's a topic for another course.

85
00:05:49,940 --> 00:05:52,850
If you'd like to learn more about them,
check the teachers notes for

86
00:05:52,850 --> 00:05:53,590
more information.

87
00:05:54,860 --> 00:05:57,040
Now, let's compile the C if
we've introduced any errors.

88
00:05:58,970 --> 00:06:02,268
Now, let's run to see the results
of adding Joe to our list.

89
00:06:04,468 --> 00:06:07,391
As you can see we were able
to add a new student and

90
00:06:07,391 --> 00:06:10,110
we maintained the sorted
order of the list.