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 are going to be comparing linear and binary search and tracing code for these searching algorithms. Welcome to today's lesson from the unit, Searching and Sorting Algorithms. This lesson is called Comparing Searching Algorithms, and by the end of today's lesson, you'll be able to compare and contrast linear and binary search, and trace the code for both searching algorithms. Shall we make a start? We will be exploring these keywords in today's lesson.

Shall we take a look at them? Algorithm, algorithm, a set of step-by-step instructions to solve a problem.

Trace table, trace table, a tool used to track the values of variables and the flow of execution in an algorithm or programme, step by step.

Look out for these keywords throughout today's lesson.

Today's lesson is split into two paths.

We'll start by comparing linear and binary search and then we'll move on to trace code for searching algorithms. Let's make it start by comparing linear and binary search.

You are looking for a word in a dictionary that starts with ca, a sample of data is shown below.

So we have cabin, cable, cabot, cacao, cache, cacti, cactus, and cadet.

Which of the searching algorithms can you use on this data? What is meant by the worst-case scenario? What is an example of a worst-case scenario from this data? Maybe pause the video whilst you have a think.

Aisha says, "A binary search could be used on this data because it's in order, but a linear search could also be used." That's right, Aisha, well done.

Sam says "The worst-case scenario is when the item you are looking for is the very last one in the list or isn't in the list at all." So Alex said, "So the worst case in this data would be if the word isn't in the list, like the word, cabaret." Well done.

That's some excellent answers.

Did you have something similar? So far you have performed linear and binary searches separately to find an item in a list.

You've also considered the worst-case scenario of both of these algorithms, i.

e.

the highest number of comparisons possible on a given list of data.

It is important you can describe the difference between these two searching algorithms so that you can recognise when one algorithm might be more suitable than another.

Sam has created a programme that stores the planets in our solar system.

So we have the elements and we have the index values shown in the table.

A linear search checks each item in a list or sequence of data one at a time to see if it's the right item.

So we'd start with position zero, which contains Earth, then move on to 1, which is Jupiter, and then Mars, Mercury, Neptune, Saturn, Uranus, and Venus.

Time to check your understanding.

Sam has created a programme that stores the planets in our solar system, which planets will be compared to the planet Neptune when Sam performs a linear search on the data shown? Pause the video whilst you have a think.

How did you get on? That's right, Earth, Jupiter, Mars, Mercury and Neptune would all be compared if Sam performed a linear search on the data shown.

A binary search discards half of the remaining data with each comparison and repeats the process until the item is found or until the data set is exhausted.

So here we have Sam's programme that contains the same list of planets as the previous example.

Which planets will be compared to the planet Neptune when Sam performs a binary search on the data shown here? Maybe pause the video whilst you have a think.

That's right, Mercury, Saturn and Neptune will be compared in a binary search.

The worst-case scenario, the highest number of comparisons for a linear search on the data would be the planet Venus and that would need eight comparisons.

The worst-case scenario or highest number of comparisons for a binary search on the data would still be the planet Venus, but it would only need four comparisons.

This means binary search would generally be faster at finding a planet in this list than linear search because the planets are sorted in order.

Okay, we are moving on to our first task of today's lesson.

I'd like you to fill out the table to compare linear and binary search.

So you've got some categories to fill in for the table.

Ordered data, so does the data need to be ordered or not? Number of comparisons and simplicity of the algorithm, so how easy is it to create or code? Pause the video whilst you have a go at the activity.

How did you get on? Did you manage to compare linear and binary search? Well done.

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

So in linear search the sequence of items in the list can be ordered or unordered.

In binary search, the sequence of items in the list must be ordered.

In the worst-case scenario for a linear search, every item in the list is compared to the search item.

If you double the amount of items in the list, then the maximum number of comparisons will also double.

For binary search, every single comparison to the search item removes half of the items in the list.

If you double the number of items in the list, you would need at most, one more comparison.

Simplicity of the algorithm.

The linear search algorithm is simpler to write, whereas the binary search algorithm is longer and more complex to write.

Remember, if you want to pause the video and add any detail to your table, you can do that now.

So we've compared linear and binary search.

Let's now move on to trace code for these searching algorithms, linear search can be coded using a programming language.

The most useful method to achieve this is to create a function which returns the location of the value being searched for or some default value if not found, so if the item is not in the list.

So we start by defining a new function for a linear search.

So we have def, which is short for define, and then we have the name of the function which we've put as linear_search.

What input data is needed for the algorithm's parameters? Maybe pause the video whilst you have a think.

That's right, the algorithm needs to receive the list of items to search through and the search items as parameters.

So we have items, search_item.

The algorithm receives a list of items and the search item as parameters.

We then start by initialising the variables, so index is set to minus 1, current is set to 0, and found is equal to false.

Index stores the index of the found item.

The value minus 1 signifies the item has not been found.

Current stores the index of the current item in the list where the value 0 means it will start from the first item in the list.

Found is a flag that is used to record whether the search item has been found or not.

We then compare the current item to the item we are searching for.

What is the condition of the selection statement? Maybe pause the video whilst you have a think.

That's right, the selection statement should use the comparison items[Current] == to search_item.

So is the current item in the list equal to the search item that's being looked for.

If the item has been found, store the current index and raise the flag.

So index is changed to current and found is changed to true.

Proceed to the next item in the list.

Move the current index onto the next element in the list by incrementing the value of current by 1, this means the algorithm will continue to go through the list until the item is found.

What is the condition of the while loop? Maybe pause the video whilst you have a think.

That's right.

The condition of the while loop should be while current < len(items) and found == False.

So the flag hasn't been raised.

So we repeat while the end of the list has not been reached and the search item has not been found.

Alex says, "What value is returned if the search item has not been found?" That's a really good question, Alex, well done.

The initial value of minus 1 indicates that the item has not been found because minus 1 isn't a value in our list.

Binary search can also be coded using a programming language.

There are a variety of ways to code binary search.

This example completes the search using iteration.

So we start by defining a new function for a binary search, def binary_search.

The algorithm receives the list of items to search and the search item as parameters.

So exactly the same as we did for our linear search algorithm.

We then initialise the variables.

Again, this is pretty similar to our linear search, but you'll notice one difference, index stores the index of the found item.

The value of minus 1 signifies the items have not been found.

This is where we got a slight difference, first and last store the indices of the first and last items in the list where the search item may be found.

Found is a flag used to record whether the search item has been found or not.

We then have to find the middle item or midpoint between the first and last item.

So midpoint is = (first + last) // by 2.

Notice the double forward slash here for floor division.

So what we are doing here is we're adding the first and last values together and then with calculating the floor division of the total by 2.

If the number of items from the first to the last is even, the midpoint is the middle-left item, we then compare the item at the midpoint to the item you are searching for.

What is the condition of the selection statement? Maybe pause the video whilst you have a think.

That's right, the condition of the selection statement is items [midpoint] == search_item.

If the item has been found, store the midpoint, i.

e.

the location that it was found and raise the flag.

So index = to midpoint, found = to True.

Otherwise check if the item at the midpoint is lower than the search item.

So elif items[midpoint] < search_item.

First is going to be equal to midpoint plus 1.

Otherwise the item at the midpoint is greater than the search item.

So we have now else: last = midpoint - 1.

We then place the statements inside a loop so that the process is repeated with the number of items between the first and last being halved in each iteration.

What is the condition of the while loop? Maybe pause the video whilst you have a think.

That's right, the condition should be, first is <= last and found == False.

So we repeat while there are still items to check between first and last and the search item has not been found.

We then return the index where the search item was found.

Okay, we are moving on to our next task of today's lesson, task B.

Complete the trace table for the linear search algorithm when the items in the list are the following names, Izzy, Lucas, Aisha, Sam, Laura, Andeep.

And the search item is Laura.

The first two passes have been completed already and your need to add more rows to the trace table.

So here's an example of the algorithm.

So you can read through and trace the code, and here is the start of the trace table.

Remember the first two passes have been completed for you.

You'll need to add more rows to the trace table.

Pause the video whilst you complete the activity.

How did you get on? Did you manage to complete the trace table? Well done.

Remember the first two passes have been completed for you.

So we are going to start our trace table on line 5.

So on line 5 of the code, the condition returns true.

On line 6 the item which is in current is Aisha and the condition returns as false.

And then on line 9, current is incremented by 1 to 3.

Here's a continuation of the trace table.

So we go back to line 5, the condition is true.

Line 6, the item in the current position is Sam, so the condition is false.

Line 9, current is incremented by 1 to 4.

Back to line 5, the condition is true.

Line 6, the item held in current is Laura, so the condition is now true.

So this time we run line 7, which means that index is equal to 4, line 8, the condition is true, and on line 9, current is incremented by 1 to 5, and then this time we run line 5, but the condition is now false because the flag has been raised.

Remember, if you need to make any corrections to your trace table, you can pause the Video and make those now.

I'd now like you to complete the trace table for the binary search algorithm.

When the items in the list are Aisha, Andeep, Izzy, Jun, Laura, Lucas, Sam, and Sophia.

And the search item is still Laura, like it was in the previous example.

Again, the first two passes have been completed already and you'll need to add more rows to the trace table.

So here's an example of the code which you can use to trace through and complete the trace table.

Here's the trace table, which has been completed with the first two passes for you.

Remember you'll need to add more rows to the trace table.

Pause the video whilst you complete the task.

How did you get on? Did you manage to complete your trace table? Well done.

I've just given you the lines of the trace table below the first two passes here.

So starting on line 6, the condition is true.

We move to line 7, and the midpoint is equal to 5, line 8, the items midpoint is Lucas and the condition is false.

Line 11, the item midpoint is Lucas and the condition is false.

On line 14, last becomes 4.

So remember we're shifting the focus.

On line 6, the condition is true.

On line 7 the midpoint becomes 4, on line 8 the midpoint item is Laura and the condition is true this time.

So we run line 9 which means index == 4, and then on line 10, found the flag gets turned to true.

And then finally on line 6 the condition of our while loop is changed to false and the programme stops.

Remember again, if you need to make any corrections to your trace table, you can do that now.

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

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

The searching algorithm you use will depend on the data and context you are using.

Coding a binary search is more complex than a linear search.

Tracing code for a searching algorithm by completing a trace table can help you to check how efficient the algorithm is.

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

Bye.