Searching Sorted Lists6:10 with Jeremy McLain
Lists can be searched much faster using BinarySearch once they're sorted.
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