[MUSIC]

[SOUND] Now that we've covered sorting algorithms,

the groundwork has been laid to talk about searching algorithms.

If you need to search through an unsorted list of items,

binary search isn't an option because you have no idea which half

of the list contains the item you're looking for.

Your only real option is to start at the beginning and

compare each item in the list to your target value,

one at a time until you find the value you're looking for.

This algorithm is called linear_search or sequential search,

because the search proceeds in a straight line or sequence.

Even though linear_search is inefficient, searching for just one name will happen so

fast that we won't be able to tell anything useful about the algorithm's

runtime.

So let's suppose we add 100 different names and

that we needed to know where they appear in a list of unsorted names.

Here is some code that demonstrates.

As usual, this code at the top isn't relevant to the search algorithm.

It's just like the code that loaded the list of numbers from a file in

the previous stage, but this code calls a different function, load_strings,

that loads a list of strings in.

If you want the load_strings Python code, we'll have it for

you in the teacher's notes.

Here's a separate hard-coded list,

containing the 100 names we're going to search for.

We'll loop through each name in this list and pass it to our search function to get

the index within the full list where it appears.

Now, let's implement the search function.

Compared to the sorting algorithms, this is going to be short.

The index of item function takes the Python list you want to search through and

a single target value you want to search for.

Now we need to loop over each item in the list.

The range function gives us a range of numbers from its first argument up to, but

not including, its second argument.

So if our list had a length of five,

this would loop over the indexes zero through four.

We test whether the list item at the current index matches our target.

If it does, then we return the index of the current item.

This will exit the index of item function without looping over the remaining items

In the list.

If we reach the end of the loop without finding the target value,

that means that it wasn't in the list.

So instead of returning an index,

we return the special Python value, None, which indicates the absence of a value.

Other languages have similar values, like nil or null.

But if yours doesn't, you might have to return a value that would otherwise be

impossible, like an index of negative one.

Now let's call our new search function.

We start by looping over the list of 100 values we're looking for.

We're using the values themselves this time, not their indexes within the list,

so there's no need to mess with Python's range function.

Here's the actual call to the index_of_item function.

We pass it the full list of names that we loaded from the file

plus the name we want to search for within that list.

Then we store the index it returns in a variable.

And lastly, we print the index we get back from the index_of_item function.

Let's save this and go to our console and see if it works.

python linear_search.pi names/unsorted.txt.

And it'll print out the list of indexes for each name.

I actually set it up so that the last two items in the list of names we're going to

search for corresponded to the first and last name within the file.

So if we open up our unsorted.txt file,

we'll see Mary Rosenberger as the first name and Alonso Viviano as the last name.

And those are the last two values in our list of names we're searching for.

So it returned an index of 0 for that second-to-last name, and

you can see that name here on line 1 of the file.

The line numbering starts at 1, and the Python list indexes start at 0, so

that makes sense.

And for the last name, we'll return an index of 109873.

And you can see that name here on line 109874.

So we can see that it's returning the correct indexes.

But right now, we're just searching for

100 different names in a list of 100,000 names.

In the real world, we're going to be looking for

many more names than that within much bigger lists than that.

Can we do this any faster?

Yes, but we'll need to use the binary search algorithm.

And for that to work, we need to sort our list of strings.

We'll do that in the next video.