**Heads up!** To view this whole video, sign in with your Courses account or enroll in your free 7-day trial.
Sign In
Enroll

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