Lesson video

Hello, my name is Mrs. Holborow, and welcome to Computing.

I'm so pleased you've decided to join me for the lesson today.

In today's lesson, we're going to be learning about the linear search algorithm.

We'll look at the steps performed during a linear search, and perform a linear search on a set of data.

Welcome to today's lesson from the unit "Searching and sorting algorithms".

This lesson is called "Linear search", and by the end of today's lesson, you'll be able to explain why computers need to search data and perform a linear search to find a position of an item in a list.

Shall we make a start? We will be exploring these keywords throughout today's lesson.

Linear search.

Linear search.

An algorithm that searches for an item in a list of items by systematically examining each item, one after another.

Best-case.

Best-case.

This scenario occurs when the item you are looking for results in the smallest possible number of steps.

Worst-case.

Worst-case.

This scenario takes place when the item you are looking for results in the greatest possible number of steps.

Look out for these keywords throughout today's lesson.

Today's lesson is broken down into two parts.

We'll start by describing how linear search finds an item.

We'll then move on to perform a linear search.

Let's make a start by describing how linear search finds an item.

Whenever there are lots of items, it's important to be able to find the one you need.

For instance, you may need to look through a clothing rail to find the item in your size, or search through a pack of cards for a particular playing card.

Computers need to be able to search through sequences of data all the time, such as trying to find a file with a particular name on your computer.

Another example is using a search engine to find websites on the internet that match certain keywords.

When faced with a search problem, you will have to either deal with ordered or unordered sequences of data.

Linear search is an algorithm that involves checking each item in a list or sequence of data one at a time to see if it's the right item.

If you have a list that is not in the right order, a linear search is the only reasonable way to search through it.

So you can see here, with this list of items, we start at the first item of the list, which holds the value four, and then we move on to the value 18, and so on.

Time to check your understanding.

A linear search can only be used on items that are in order.

Is this true or false? Pause the video whilst you have a think.

Did you select false? Well done.

A linear search can be used on items that are in order or not in order.

If you have a list that is not in order, a linear search is the only reasonable way to search through it.

The instructions for performing a linear search can be written as, step one, take a list of data and an item that is being searched for, the search item.

Two, start from the first item in the list.

Three, compare the item at the current position to the search item.

Four, if it is not the item you are searching for, then go to the next item in the list.

Five, if the item at the current position is equal to the search item, then stop searching.

If steps one to five are completed and the search item is not found, then the item is not in the list.

Each number is hidden under a cup.

The cups are arranged in a random order.

From the cups, the number to find or the search item is 126.

So you can see we have nine cups in total.

The first step of the linear search algorithm is to take a list of data and the item that is being searched for, the search item.

So we have our list of nine cups, and we have our search item, which is 126.

We then start from the first item in the list.

So cup one is our first item, and is going to become our current item.

Cup one holds the value 27.

So we compare 27 to the search item, which is 126.

So we move on to cup two, because the item we were searching for was not in cup one.

So we go to the next item in the list, which is cup two, and that becomes current.

Cup two holds the value 358.

Remember, we're going to compare this value to the search item.

If this is not the item you are searching for, then we go to the next item in the list, cup three.

Cup three contains 62.

We compare that to our search item of 126.

If it is not the item we're searching for, then we go to the next item in the list, cup four.

Cup four holds nine.

So we compare this value to the search item 126.

If it's not the item we're searching for, then we go to the next item in the list, cup five.

Cup five holds the value 412.

We compare this to our search item of 126.

If it's not the item we're searching for, then we go to the next item in the list, which is cup six.

Cup six contains 126.

So we compare the item at the current position to the search item.

If the item at the current position is equal to the search item, then we stop searching, because we found the item we were looking for.

Time to check your understanding.

Put the steps of a linear search algorithm into the correct order.

Pause the video whilst you read the steps carefully and put them in the correct order.

How did you get on? Did you manage to put the steps in the correct order? Well done.

Let's have a look at the answers together.

So, step one is to take a list of data and an item that is being searched for, the search item.

Step two is to start from the first item in the list.

Step three, compare the item at the current position to the search item.

Step four, if it is not the item you're searching for, go to the next item in the list.

And finally, step five, if the item at the current position is equal to the search item, then stop searching.

Okay, we're moving on to our first task of today's lesson, and you've done a fantastic job so far, so well done.

I'd like you to describe the steps needed if a linear search was used to find the two of spades card in this list of cards.

So the list is the four of spades, 10 of spades, five of spades, two of spades, eight of spades, seven of spades, nine of spades, and then the three of spades.

How did you get on? Did you manage to describe the steps needed if a linear search was used to find the two of spades card in this list of cards? Well done.

Let's have a look at a sample answer together.

The linear search item will start with the list of data, or cards, and the search item, which in our case is the two of spades.

Starting with the first item in the list, the item at the current position will be compared to the search item.

So we start by comparing the four of spades to the two of spades.

As this is not the item we're searching for, the algorithm will go to the next item in the list and repeat the process until the item at the current position is equal to the search item, the two of spades.

Did you have a similar answer? Remember, if you need to pause the video to add any detail to your answers, you can do that now.

Okay, so we've described how a linear search finds an item, but let's move on now to perform a linear search on a set of data.

You are now going to perform a linear search on a set of cards.

Take eight cards and choose a card to search for.

Shuffle the cards thoroughly.

Place the cards face down in a single row without looking at them.

Perform a linear search for your chosen card and fill in the table.

Repeat steps one to four, two or three times.

The rules are, you can only turn over one card at a time, and you must turn it back after each comparison.

Sam says, "My search card was the first one I turned over." That was lucky, Sam! Jun says, "My search card was the last card I turned over." Oh, that's not so lucky, Jun.

In the last activity, you may have noticed that the amount of cards you had to compare for your search card wasn't always the same.

In computer science, it's useful to know how long an algorithm may take to complete under different scenarios.

The number of steps an algorithm needs to perform, depending on the input data, can be expressed as the best-case or worst-case scenario.

The best-case scenario occurs when the item you are looking for results in the smallest possible number of steps.

In the case of linear search, this happens when the item you are looking for is the very first one in the list.

So in this case, the card the four of spades would be the best-case scenario.

The worst-case scenario takes place when the item you are looking for results in the greatest possible number of steps.

With the linear search, this happens when the item you are looking for is the very last one in the list, or isn't in the list at all.

So in this case, the card the six of spades would be the worst-case scenario, or a card that isn't in the list at all.

So for example, the card the three of spades.

Time to check your understanding.

What card would be the best-case scenario in this linear search? Is it A, the three of spades? B, the two of spades? Or C, the four of spades? Pause the video whilst you have a think.

Did you select C, the four of spades? Well done.

The four of spades is the first item in the list, so that's going to be the best-case scenario.

How many comparisons would it take to work out that the card the six of spades wasn't in this set of cards? Pause the video whilst you have a think.

How did you get on? You would need to perform eight comparisons, as the whole list would need to be checked, and the list contains eight items. Sam says, "So far we've only seen linear searches on lists that contain numbers.

Does the linear search only work on numbers?" That's a really good question, Sam.

A linear search does not just work on lists containing numerical values.

It can also be used on lists containing any type of data.

So for example, strings.

Okay, we're moving on to our second task of today's lesson, task B.

Aisha has created a programme that stores all of the cities that customers of a travel shop visited last year.

A sample of data is shown in figure one.

So figure one contains the list items, Moscow, Sydney, Beijing, Athens, Mumbai, Tokyo, and Prague.

For part one, list the cities that will be compared to the city Athens when performing a linear search on the data shown in figure one.

So the search item is Athens.

For two, state the number of comparisons that will be made when performing a linear search for the city Mumbai on the data shown in figure one.

And for part three, state the number of comparisons that will be made when performing a linear search for the city Berlin on the data shown in figure one.

Pause the video here whilst you complete the activities.

How did you get on? Did you manage to answer the questions and perform a linear search? Well done.

Let's have a look at the sample answers together.

For part one, you were asked to list the cities that would be compared to the city Athens when performing a linear search on the data shown in figure one.

The cities that would be compared would be Moscow, Sydney, Beijing, and Athens.

Remember, the linear search algorithm stops when it finds the search item.

For part two, you were asked to state the number of comparisons that will be made when performing a linear search for the city Mumbai on the data shown in figure one.

There would be five comparisons.

Moscow, Sydney, Beijing, Athens, and Mumbai.

For part three, you were asked to state the number of comparisons that will be made when performing a linear search for the city Berlin on the data shown in figure one.

Seven comparisons would be made.

Moscow, Sydney, Beijing, Athens, Mumbai, Tokyo, and Prague, because Berlin isn't in the list, so the algorithm would need to check the whole list before returning that it didn't find the item.

The performance of an algorithm relates to the number of steps it takes to complete.

Another sample of data is shown in figure two.

So we have some more cities, Dublin, Cairo, La Paz, Seoul, New York, London, and Paris.

For part one, which city would you search for to incur the best-case scenario in figure two? For part two, how many comparisons would need to be made in the best-case scenario in figure two? For part three, which city would you search for to incur the worst-case scenario in figure two? And for part four, how many comparisons would need to be made in the worst-case scenario in figure two? Pause the video whilst you have a go at the task.

How did you get on with the activity? Did you manage to discover the best and worst-case scenarios? Well done.

For part one, you were asked, which city would you search for to incur the best-case scenario in figure two? The city would be Dublin, because that's the first item in the list.

For part two, how many comparisons would need to be made in the best-case scenario in figure two? It would be one comparison.

For part three, which city would you search for to incur the worst-case scenario in figure two? The worst-case scenario would be Paris, or any other city that is not in the list.

And then finally, for part four, how many comparisons would need to be made for the worst-case scenario in figure two? It would be seven, because there's seven items in the list.

Remember, if you need to make any corrections to your answer, you can pause your video and do that now.

Okay, we've come to the end of today's lesson, linear search, and you've done a great job today, so well done.

Let's summarise what we've learned together in this lesson.

Linear search is an algorithm that involves checking each item in a list or sequence of data, one at a time, to see if it's the item being searched for.

Linear search is able to find items that are in any order, so they can be sorted or unsorted.

The best-case scenario for a linear search is when the search item is the very first one in the list.

The worst-case scenario of a linear search is when the item you are looking for is the very last one in the list, or isn't in the list at all.

I hope you've enjoyed today's lesson, and I hope you'll join me again soon.

Bye!.