Lesson video

Hi, I'm Kash, your computer science teacher for the algorithms unit.

In this lesson, we're going to be looking at the linear search.

For this lesson, you need a pen, some paper and you're going to need to remove any distractions that are going to get in your way of focusing.

Once you've done that, let's begin.

Searching for a book.

Think about how you would instruct someone to find a book, on a randomly ordered bookcase in someone's bedroom or in the fiction section at a library.

Would the instructions be the same in both cases? Write your answers down.

Okay, so the instructions would differ depending on the order of the books.

So if it's random, you might implement a different set of instructions, as opposed to if they were in a ordered manner, such as a library and most libraries, they've got their own system to enable you to find books.

In this lesson you will, identify why computers often need to search data, describe how linear search is used for finding the position of an item in the list of items and perform a linear search to find the position of an item in the list.

Searching for an item.

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

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

Computers need to search through sequences of data all the time.

For example, if you're trying to find a file with a particular name on your computer, you might implement an algorithm.

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 either have to deal with, ordered or unordered sequences of data.

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

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

In the next slide, you'll see an example of how to perform a linear search.

Each item is hidden under a cup or each number is hidden under a cup.

The cups are arranged in a random order.

From the cups, the number to find is 126.

So as we can see there, we've got nine cups, under each cup is a number and we're looking for the number 126.

Take a list of data and an item that is being searched for, the search item.

Start from the first item in the list.

So the current item.

Compare the item at that current position to the search item.

So we're comparing 27 with 126.

If it is not the item you're searching for go to the next item in the list.

Compare the item at the current position to the search item.

So as you can see the current position's moved from cup one because the number in there was not the one we were looking for so now the current position is under cup two and once again, is not the number that we're looking for.

If it's not the item you're searching for, go to the next item in the list.

Compare the item at the current position to the search item.

We've got 62 which is not 126.

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

This time we've got nine.

We are comparing the item at the current position to the search item.

If it's not the item you're searching for, go to the next item in the list, cup number five, 412.

We've compared it, it's not the correct item.

We're moving on to the next cup and under that cup, we've got 126, the number we're looking for is 126 so if the item at the current position is equal to the search item, stop searching because we don't need to continue.

We've found what we're looking for.

Algorithm for linear search.

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

Two, repeat steps a to c, starting from the first item in the list, until you find the search item or until you are at the end of the list or the end of the list is reached.

So A, compare the item at the current position to the search item.

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

Otherwise, continue and go on to the next item in the list.

Task one, searching shuffled cards.

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

Take 10 cards and choose a card to search for.

Shuffle the cards thoroughly.

Play six of the 10 cards face down in a single row without looking at them.

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

Rules, you can only turn over one card at a time.

You must turn it back over after each comparison.

Pause the video to complete your task.

Task one, searching shuffled cards.

Using the worksheet, complete task one.

Resume once you're finished.

Performance of an algorithm.

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

In computer science, it is 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 and worst-case scenario.

Best-case scenario occurs when the item you're looking for results in the smallest possible number of steps.

In the case of linear search, this happens when the item you're looking for is the very first on the list.

So for example, in this set of cards, if you're looking for the four of spades or the four, if the best case is if it's the first card, we turn around.

Worst-case scenario.

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

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

So in this scenario at the bottom there, the six of spades or the six would be the worst case because it's the last one that we're searching.

Pause the video to complete your task.

Task two, carrying out a linear search.

Using the worksheet complete task two.

There are three parts.

Searching for a city, best and worst-case scenarios on linear search algorithm.

Resume once you're finished.

Best and Worst-case scenario.

Answer the questions below about performing a linear search on these cards.

What card would you need to search for, for the best-case scenario to occur? What card would give you the worst-case scenario? And how many comparisons would it take to work out that the card wasn't in the set of cards? Write your answers down.

Okay, so for the best case scenario to occur, we would need the six of spades because it's the first item that we're searching.

and straightaway, we found what we're looking for.

The card with the worst case scenario would be the eight of spades 'cause it's the last card in that list of cards and how many comparisons would it take? So we've got six of spades which is one, seven spades which is two, four spades, 10 spades, two spades, nine spades , five spades, A spades, so it would be at least eight.

So we're doing eight comparisons and then if we haven't found the card, that's how many it would take.

Task three, create a flowchart for a linear search.

Using the instructions below, create a flowchart.

Take a list of data and an item that's being searched for, the search item.

Repeat steps a to c starting from the first item in the list, until you find the search item until the end of the list is reached.

So Part A is compare the item at the current position to the search item.

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

C, otherwise, go to the next item in the list.

Pause the video to complete your task.

Task three, linear search flowchart.

Using the worksheet, complete task four.

Resume once you're finished.

Task three, solution.

So here we have a flowchart.

So we've got our start Terminator.

We are initialising i to be equal to zero, by inputting our search and inputting our items. So the reason why we initialise the i to zero, is to see and to make sure that there is a list of items that we're searching through and to make sure that once we've searched all of them, that once it becomes false, that we end this algorithm but whilst it's true, we're then going to compare the items in the list to the value that we're looking for.

If it's true, we're going to output and say it's been found.

If it's false, we're going to iterate or add one to i and then we're going to keep looping around this list until the item has either been found or we've finished looping through the list, the list is complete and the item has not been found.

How did you get on with the algorithm? You learn about the flowchart symbols so I'd be really impressed to see, the flowcharts that you've created for the linear search algorithm.

Thank you for joining me on this lesson.

Share your work with Oak National.

If you'd like to, ask a parent or carer to share your work on Instagram, Facebook or Twitter, tagging @OakNational and #LearnwithOak.

Thank you very much for joining me today and hopefully I will see you on the next lesson, where we're going to be looking at the binary search.

Thank you very much and goodbye.