Linear Search

[MUSIC] 0:00 [SOUND] Now that we've covered sorting algorithms, 0:04 the groundwork has been laid to talk about searching algorithms. 0:07 If you need to search through an unsorted list of items, 0:10 binary search isn't an option because you have no idea which half 0:13 of the list contains the item you're looking for. 0:17 Your only real option is to start at the beginning and 0:20 compare each item in the list to your target value, 0:23 one at a time until you find the value you're looking for. 0:25 This algorithm is called linear_search or sequential search, 0:29 because the search proceeds in a straight line or sequence. 0:33 Even though linear_search is inefficient, searching for just one name will happen so 0:36 fast that we won't be able to tell anything useful about the algorithm's 0:40 runtime. 0:44 So let's suppose we add 100 different names and 0:45 that we needed to know where they appear in a list of unsorted names. 0:47 Here is some code that demonstrates. 0:51 As usual, this code at the top isn't relevant to the search algorithm. 0:53 It's just like the code that loaded the list of numbers from a file in 0:57 the previous stage, but this code calls a different function, load_strings, 1:00 that loads a list of strings in. 1:05 If you want the load_strings Python code, we'll have it for 1:06 you in the teacher's notes. 1:10 Here's a separate hard-coded list, 1:11 containing the 100 names we're going to search for. 1:13 We'll loop through each name in this list and pass it to our search function to get 1:16 the index within the full list where it appears. 1:20 Now, let's implement the search function. 1:23 Compared to the sorting algorithms, this is going to be short. 1:25 The index of item function takes the Python list you want to search through and 1:29 a single target value you want to search for. 1:33 Now we need to loop over each item in the list. 1:36 The range function gives us a range of numbers from its first argument up to, but 1:39 not including, its second argument. 1:43 So if our list had a length of five, 1:46 this would loop over the indexes zero through four. 1:47 We test whether the list item at the current index matches our target. 1:51 If it does, then we return the index of the current item. 1:56 This will exit the index of item function without looping over the remaining items 1:59 In the list. 2:03 If we reach the end of the loop without finding the target value, 2:04 that means that it wasn't in the list. 2:08 So instead of returning an index, 2:09 we return the special Python value, None, which indicates the absence of a value. 2:11 Other languages have similar values, like nil or null. 2:17 But if yours doesn't, you might have to return a value that would otherwise be 2:20 impossible, like an index of negative one. 2:23 Now let's call our new search function. 2:26 We start by looping over the list of 100 values we're looking for. 2:28 We're using the values themselves this time, not their indexes within the list, 2:32 so there's no need to mess with Python's range function. 2:36 Here's the actual call to the index_of_item function. 2:40 We pass it the full list of names that we loaded from the file 2:43 plus the name we want to search for within that list. 2:46 Then we store the index it returns in a variable. 2:48 And lastly, we print the index we get back from the index_of_item function. 2:52 Let's save this and go to our console and see if it works. 2:56 python linear_search.pi names/unsorted.txt. 3:00 And it'll print out the list of indexes for each name. 3:09 I actually set it up so that the last two items in the list of names we're going to 3:13 search for corresponded to the first and last name within the file. 3:17 So if we open up our unsorted.txt file, 3:21 we'll see Mary Rosenberger as the first name and Alonso Viviano as the last name. 3:23 And those are the last two values in our list of names we're searching for. 3:31 So it returned an index of 0 for that second-to-last name, and 3:35 you can see that name here on line 1 of the file. 3:39 The line numbering starts at 1, and the Python list indexes start at 0, so 3:42 that makes sense. 3:46 And for the last name, we'll return an index of 109873. 3:48 And you can see that name here on line 109874. 3:54 So we can see that it's returning the correct indexes. 3:58 But right now, we're just searching for 4:01 100 different names in a list of 100,000 names. 4:03 In the real world, we're going to be looking for 4:06 many more names than that within much bigger lists than that. 4:08 Can we do this any faster? 4:11 Yes, but we'll need to use the binary search algorithm. 4:13 And for that to work, we need to sort our list of strings. 4:17 We'll do that in the next video. 4:20