[MUSIC]

So far we've spent a lot of time in theory, and

while these things are all important things to know, you get a much

better understanding of how algorithms work when you start writing some code.

As I mentioned earlier, we're going to be writing Python code in this and

all subsequent algorithm courses.

If you do have programming experience but in another language,

check the Notes section of this video for an implementation in your language.

If you don't have any experience, I'll try my best to explain as we go along.

On the video you're watching right now, you should see a Launch Workspaces button.

We're going to use a Treehouse coding environment, called Workspaces,

to write all of our code.

If you're familiar with using Python in a local environment,

then feel free to keep doing so.

Workspaces is an in-browser coding environment, and we'll take care of all

the setup and installation so you can focus on just writing and evaluating code.

Workspaces is quite straightforward to use.

On the left here, we have a File Navigator pane,

which is currently empty since we haven't created a new file.

On the top, we have an Editor where we write all our code.

And then below that, we have a terminal, or a command line prompt,

where we can execute the scripts that we write.

Let's add a new file here.

So at the top, in the Editor area, we're going to go to File > New File.

And we'll name this linear_search.py.

In here,

we're going to define our linear_search algorithm as a stand-alone function.

We start with the keyword def, which defines a function or a block of code.

And then we give it the name, linear_search.

This function will accept two arguments.

First, the list we're searching through, and

then the target value we're looking for.

Both of these arguments are enclosed in a set of parentheses, and

there's no space between the name of the function and the arguments.

After that, we have a colon.

Now, there might be a bit of confusion here.

Since we already have this target value, what are we searching for?

And like the game we played at the beginning,

where John's job was to find the value, in a true implementation of linear_search,

we're looking for the position in the list where the value exists.

If the target is in the list, then we return its position.

And since this is a list, that position is going to be denoted by an index value.

Now, if the target is not found, we're going to return None.

The choice of what to return in the failure case may be different in other

implementations of linear_search.

You can return -1, since that isn't typically an index value.

You can also raise an exception, which is Python speak for

indicating an error occurred.

Now, I think for us,

the most straightforward value we can return here is None.

Now, let's add a comment to clarify this, so hit Enter to go to the next line.

And then we're going to add three single quotes,

and then below that on the next line, we'll say,

Returns the index position of the target if found, else returns None.

And then on the next line, we'll close off those three quotes.

This is called a docstring and is a Python convention for documenting your code.

The linear_search algorithm is a sequential algorithm that compares each

item in the list until the target is found.

To iterate, or loop, or walk through our list sequentially,

we're going to use a for loop.

Now, typically when iterating over a list in Python, we would use a loop like this.

We'd say for item in list.

This assigns the value at each index position to that local variable item.

We don't want this, though, since we primarily care about the index position.

Instead, we're going to use the range function in Python to create

a range of values that start at 0 and end at the number of items in the list.

So we'll say, for i, i stands for index here, in range,

starting at 0, and going all the way up to the length of the list.

We can get the number of items in the list using the len function.

Now, going back to our talk on complexity and

how individual steps in an algorithm can have its own run times,

this is a line of code that we would have to be careful about.

Python keeps track of the length of a list, so this function call here,

len(list), is a constant-time operation.

Now, if this were a naive implementation, let's say we wrote the implementation

of the list, and we iterate over the list every time we call this length function,

then we've already incurred a linear cost.

Okay, so once we have a range of values that represent indexed positions in this

list, we're going to iterate over that using the for loop and

assign each index value to this local variable i.

Using this index value,

we can obtain the item at that position using subscript notation on the list.

Now, this is also a constant-time operation because the language says so.

So we'll do if list, so once we have this value,

which we'll get by using subscript notation, so we'll say list[i].

Once we have this value, we'll check if it matches the target.

So if the value at i == target, well, if it does,

then we'll return that index value cuz we want the position.

And once we hit this return statement, we're going to terminate our function.

If the entire for loop is executed, and we don't hit this return statement,

then the target does not exist in the list.

So at the bottom here, we'll say return None.

Even though all the individual operations in our algorithm run in constant time,

in the worst-case scenario this for loop here will have to go through

the entire range of values and read every single element in the list.

Therefore giving the algorithm a big old value of N, or running in linear time.

Now, if you've written code before,

you've definitely written code like this a number of times, and I bet you didn't know

that all along you were implementing what is essentially a well-known algorithm.

So I hope this goes to show you that algorithms are a pretty

approachable topic.

Like everything else, this does get advanced, but

as long as you take things slow, there's no reason for it to be impossible.

Remember that not any block of code counts as an algorithm.

To be a proper implementation of linear_search, this block of code must

return a value, must complete execution in a finite amount of time, and

must output the same result every time for a given input set.

So let's verify this with a small test.

Let's write a function called verify that accepts an index value.

If the value is not None, it prints the index position.

If it is None, it informs us that the target was not found in the list.

So def verify, and this is going to take an index value.

And we'll say, if index is not None,

then we'll print Target found at index.

Whoops, that's a colon here.

Index, else, that needs to go back.

There we go, else, we'll say,

Target not found in list.

Okay, using this function, let's define a range of numbers now.

So this will be a list numbers, and we'll just go from 1 to, let's say, 10.

Now, if you've written Python code before, you know that I

can use a list comprehension to make this easier, but we'll keep things simple.

We can now use our linear_search function to search for

the position of a target value in this list.

So we can say result = linear_search.

And we're going to pass in the numbers list,

that's the one we're searching through.

And we want to look for the position where the value 12 exists.

And then we'll verify this result.

If our algorithm worked correctly,

the verify function should inform us that the target did not exist.

So make sure you save the file, which you can do by going up to File, and

Save, or hitting Cmd+S.

And then below in the terminal, you're gonna type out python linear_search,

or you can hit Tab and it should auto-complete, linear_search.py.

As you can see, correct, the target was not found in the list, so

the output of our script is what we expect.

For a second task, let's search for the value 6 in the list.

So you can copy this, Cmd+C to copy, and then paste it again, and

we'll just change 12 here to 6.

And then come back down to the terminal,

hit the up arrow to execute the same command again, and hit Enter.

You'll notice that I forgot to hit Save, so it did not account for that new change.

We'll try that again, and there you'll see that if it works correctly,

which it did, the index should be number 5.

Run the program on your end, and make sure everything works as expected.

Our algorithm returned a result in each case, it executed in a finite time, and

the results were the ones we expect.

In the next video, let's tackle binary search.