- [Craig] In this video, we consider one of the classic algorithms in computer science, the linear search.
(uplifting piano jingle)
The linear search can be performed on data in memory,
perhaps stored in arrays or lists, and data stored in files as well.
The algorithm is very straightforward.
Starting from the beginning of the data set, each item is checked in turn to see if it's the one being searched for.
It doesn't require the data to be in any order, unlike another type of search, the binary search.
It will work on any type of storage device and can be efficient for small data sets.
However, it's very inefficient for large data sets.
If you've watched one of our previous videos on algorithmic thinking,
you'd have seen that we used a linear search in that situation.
We were trying to find a word in a word search, where each letter is stored in a grid.
We examined each letter in turn to see if it matched the first letter of the word we were looking for.
And if not, we moved on to the next letter and the next and the next until we found a match.
This is a classic example of a linear search.
It didn't require the letters to be in any order, which is just as well because that's the very nature of a word search.
We can apply a linear search to a whole variety of contexts.
One might be looking for a particular box of cereal on a shelf in a supermarket.
We could go through each box one at a time until we find the one we're looking for.
We then take the box to the checkout and the computer will scan the barcode,
and then it needs to look up the product description and price in a database of products.
It could do this by starting at the first product
and comparing the barcode to see if it matches the one in the database,
and if not, it could keep checking the next one and the next one until it finds the product,
or it's not in the list at all.
So, if we apply some algorithmic thinking, we can uncover the algorithm for this particular search.
We can have a Boolean variable called found that sets to false initially because we have to find the item in the list.
We could then have a variable, i, which is the index of the item we're looking for.
We could say while it's not been found and we're not at the end of the data set,
check each item in the list.
We could do this with a simple IF statement and say if item i is equal to the item to find then
found is true, and we can output the item.
And if not, then we increment i by 1
and keep checking the next item and then the next and then the next
until we've reached the end of the list or the item has been found.
The GCSE specification states that you must be able to understand the main steps of each algorithm,
understand any prerequisites of an algorithm,
apply the algorithm to a data set
and identify an algorithm if given the code for it.
However, you're not require to remember the code for these algorithms.
In the rest of this video, we're going to work through some actual code for this algorithm.
While it's important and you need to be able to spot this code,
don't get too worried about remembering it line for line.
So in Python code, the solution might look something like this.
We're storing the data for our products in a two-dimensional list
so we can store the description and the price.
We've then got a variable called found, which we'll set to false initially,
and the index of the item to be 0.
We're asking the user, what's the product they want to find?
And while that's not been found and we haven't reached the end of the data set,
we're going to check if the product matches the one we're looking for.
And if it does, we're going to print to the screen the price with two decimal places and set found to be true
because we don't need to check any other products.
This makes the algorithm just a little bit more efficient.
If the product was not found, we can increment i by 1.
We know that algorithms are some of the hardest parts of any computer science specification,
so we've written a book called Essential Algorithms for A Level Computer Science, which is available on Amazon.
While the title of the book suggests this is only for A Level, you can see here from the examination board mapping page
that we have chapters which cover every algorithm you're required to know for the GCSE.
This book then would be perfectly appropriate for you to use
and also to take on to A Level should you choose to carry on studying the subject.
Every chapter is presented in the same way.
We introduce the algorithm from a high-level perspective and provide a link to our videos.
We then lay out the algorithm in simple-structured English so you can get your head around it.
We illustrate the algorithm in the form of a diagram and then provide an example of stepping through it.
All of these steps are designed to really get you to understand the algorithm before we present you with pseudocode.
After the pseudocode, we present you with actual code written in both Python and Visual Basic,
which you could type in and try for yourself.
(uplifting piano jingle)