Binary Search5:18 with Jay McGavren
Now that we have our list of names sorted, we can use the Binary Search algorithm on it. Let's see if we can use it to speed up our search for the indexes of 100 names.
See the instruction step following this video for the code!
Now that we have our list of names sorted, 0:00 we can use the binary search algorithm on it. 0:02 Let's see if we can use it to speed up our search for the indexes of 100 names. 0:04 Binary search keeps narrowing down the list until it has the value 0:09 it's looking for. 0:13 It's faster than linear search because it discards half the potential 0:14 matches each time. 0:18 Our code here at the top of our binary search script is unchanged from 0:19 the previous scripts. 0:22 We just call the load strings function to load our 100,000 sorted names from a file. 0:23 Here we've hard coded the list of 100 names we're going to sort for again. 0:28 It's identical to list from a linear search script, 0:32 except that I've again changed the last two names to correspond to the names 0:35 on the first and last lines of the file we'll be loading. 0:38 Now let's write the function that will implement our binary search algorithm. 0:42 Like the linear search function before, it will take two arguments. 0:46 The first is the list we're going to search through, and 0:49 the second is the target value we'll be searching for. 0:52 Again, the binary search function will return the index it found the value at, or 0:55 the special value none if it wasn't found. 1:00 Binary search is faster than linear search because it discards half the values it 1:02 has to search through each time. 1:06 To do this, 1:08 it needs to keep track of a range that it still needs to search through. 1:09 To start, that range is going to include the full list. 1:13 The first variable will track the lowest index in the range we're searching. 1:16 To start it's going to be zero, the first index in the full list. 1:20 Likewise, the last variable will track the highest index in the range we're 1:25 searching. 1:29 To start, we'll set it to the highest index in the full list. 1:29 If the first and last variables are equal, 1:33 then it means the size of the search range has shrunk to zero and there is no match. 1:35 Until that happens though, we'll keep looping to continue the search. 1:40 We want to divide the list of potential matches in half each time. 1:44 To do that, 1:47 we need to check the value that's in the middle of the range we're searching in. 1:48 We add the indexes in the first and 1:52 last variables, then divide by two to get their average. 1:54 We might get a fractional number, which can't be used as a list index, so 1:58 we also round down using Python's double-slash floor division operator. 2:01 All this will give us the index of the list element 2:07 that's the midpoint of the range we're searching. 2:09 We store that in the midpoint variable. 2:12 Whoops, looks like my indentation got mixed up there. 2:14 Let me fix that real quick. 2:18 There we go. 2:19 Now we test whether the list element at the midpoint matches the target value. 2:20 If it does, we return the midpoint index without looping any further, 2:28 our search is complete. 2:32 Otherwise, if the midpoint element's value is less than the target value, Then 2:34 we know that our target value can't be at the midpoint or any index prior to that. 2:41 So we move the new start of our search range to just after the old midpoint. 2:46 Otherwise, the midpoint element's value must have been greater than 2:51 the target value. 2:54 We know that our target value can't be at the midpoint, or any index after that, so 2:56 we move the new end of our search range to just before the old midpoint. 3:00 By unindenting here, we mark the end of the loop. 3:05 If the loop completes, 3:07 it means the search range shrank to nothing without our finding a match. 3:09 And that means there's no matching value in the list. 3:12 So we return the special Python value none to indicate this. 3:15 Lastly, just as we did in our linear search script, 3:19 we need to search for each of the 100 names. 3:22 We loop over each name in our hard-coded list. 3:25 And we call the binary_search function with the sorted list of names we're going 3:28 to load from the file and the current name we're searching for. 3:32 We have store the returned list index in the index variable. 3:36 And finally, we print that variable. 3:40 Let's save this and go to our console and try running it. 3:44 Python binary_search.py, and 3:47 it's important to give it the name of the sorted file. 3:51 If it loads the unsorted file, the binary search won't work. 3:53 So names/sorted,text. 3:56 Again, it prints out the list of indexes for each name. 4:00 I once again set it up so the last two items in the list of names we are gonna 4:05 search for corresponded to the first and last name in the file. 4:09 So it returned an index of zero for the second to last name. 4:12 And you can see that name. 4:18 Here's the second to last name, Aaron Augustine. 4:24 You can see that name here on line one of the file. 4:29 And for the last name, it returned an index of 109873. 4:32 And you can see that name here on line 109874. 4:37 Let's check the third to last name for good measure. 4:45 It looks like an index of 97022 was printed for that name, Stephen Deras. 4:48 Let's search for Steven Deras within the file. 4:56 And here it is, on line 97023. 5:01 Remember that line numbers start on one instead of zero, 5:05 so this actually matches up with the printed list index of 97022. 5:09 It looks like our binary search script is working correctly. 5:14
You need to sign up for Treehouse in order to download course files.Sign up