Lesson video

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

In this lesson, we're going to be comparing searching algorithms. For this lesson, you're going to need a pen, some paper and you're going to need to remove any distractions that didn't get in your way of focusing.

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

Searching for a word.

You are looking for a particular word in a dictionary that starts with Ca a sample of the data is shown below.

So we got cabin, cable, Cabot, cacoa, cache, cacti, cactus, and cadet.

Which of the searching algorithms can you use on this data? What is meant by the worst-case scenario? and give an example of a worst-case scenario from this data.

Write your answers down.

Okay, let's go through the answers.

So, this data you could use the linear search or the binary search.

Both of them would work for searching this list.

Why? Because it's audit and binary search only works with audit linear search co-work with audit or on audit what is meant by the worst case scenario? So if I was using the linear search and the word I was looking for was cadet that would be the worst case scenario because it would take the most number of attempts to try and find that piece of data.

So that's the worst case scenario and give an example of the worst case scenario.

So it'd be cadet for the linear search.

For binary search, we would go straight down the middle.

So because we've got one, two, three, four five, six, seven, eight, remember what we've said we'd go to the middle left item.

So we would go with cacoa.

So that would be one.

And then from there if it wasn't in that list, we'd eliminate it.

So we've got the round side that we've got cable.

If it wasn't cable, it used to be cabin or cabot.

Okay.

Let's have a look.

What we're going to do for this lesson.

In this lesson, you will interpret the code for linear search and binary search, compare the features of linear and binary search and decide which is most suitable in a given context, trace code for both searching algorithms with input data.

Comparing linear and binary search.

So far, you have performed linear and binary searches separately to find an item in a list.

You have also considered the worst case scenario for both of these algorithms, which is the greatest number of comparisons possible for a given list of data.

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

We've got a table here that breaks it down.

So we've got the linear search, we've got the binary search and we're looking at all the data, number of comparisons and simplicity of the algorithm.

So with the linear search, in regards to all the data the sequence of items in the list can either be ordered or unordered.

However, with binary search, the sequence of items in the list must be in order, In regards to the number of comparisons with linear search in the worst case scenario every item in the list is compared to the search item.

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

In regards to the 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 need at most one more comparison.

And in respect to the simplicity of the algorithm the linear search algorithm is simpler to write.

The binary search algorithm is longer and more complex.

Task one, "linear and binary searches".

Next, you will see some of these differences in practise pause video to complete your task.

Task one, "linear and binary searches".

Using the worksheet complete task one.

Resume once you're finished.

Code for linear search.

We're not going to look at the Python code for the linear search algorithm.

On the left-hand side, will be the code blocks.

On the right hand side, will be some explanations for you to follow along.

So it's tying off this algorithm by defining a new function for linear search.

We're, then going to have to put some parameters into them brackets.

So what input data do you think is needed for the algorithms parameters? We're going to be using items, so the list of the items in the list and the search item that we're looking for.

So the algorithm receives a list of items on the search item as parameters within groupie, initialise the variables.

So we're going to set them to what they are other star.

So index stalls, the index of the found item, the value minus one, signifies that the item has not been found.

That can be really important in the end.

If we don't find the item in terms of what's going to be output.

Current stores the index of the current item in the list.

The values zero means that I will start from the first item in the list.

Just like we we're dealing with strings.

The first letter of that string is always index zero.

One way that I like to remember this or one way that I kind of deliver this is when you go to a building, so a hotel to a school or to any kind of skyscraper you always start off on ground level.

So you always start from ground level.

So zero, and then if you were to get the stairs or the elevator you'd go to the first floor, second floor and so on.

And we're initialising found.

So found is a flag.

So we're using it to record if the search item has been found or not.

What is the condition of the selection statement? What do you think we'd put in there? In the selection statement, where stating that if the item that we're currently looking up is equal to the search item, we're going to be doing something.

So we're comparing the current item to the item that's being searched for.

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

So we found the item well done or all completed.

The selection statement is placed inside a loop so that the items in the list are checked one after the other.

Proceed to the next item in the list.

So move the current index onto the next element in the list by incrementing the value of current by one.

So this only happens if the items not being found.

So if it has been found, the flag been raised we've come out of this loop.

However, if it hasn't been found by incrementing the numbers and we're going to keep on searching.

What is the condition of the while loop? We're repeating while the end of the list has not been reached on the search item has not been found.

So until we get to the end of the list until we find the item we're going to keep repeating the instructions within the while loop.

What should happen once the end of the list is reached? Hint: This is a function, not a procedure.

What do you think? Because it's a function, we have to return something.

So here we're returning index.

So return the index where the search item was found.

What value is returned If the search item has not been found? we discussed this at the start.

So we've not found the search item what we're going to be returning.

Yes.

The initial value of minus one indicates that the item has not been found.

Task two.

"Code for linear search".

The next task contains two versions of the linear search algorithm written in Python.

Pause the video to complete your task.

Task two, "code for linear search".

Using the worksheet complete task two.

Resume once you're finished.

Code for binary search.

So just like we went through the linear search algorithm we're going to do the exact same for the binary search algorithm.

On the left hand side, we've got the Python code.

On the right hand side, we've got a walkthrough of what's happening.

So first we're starting off exactly the same defining a new function for binary search.

What input data is needed for the algorithms parameters? What do you think? Okay, so the algorithms parameters is the exact same.

So we've got our list of items. And then we've got the search item that we're looking for.

Once again, we're initialising the variables.

So we've got an index we've been through this.

So it stores the index of the found item minus one signifies that the items that have been found then we've got a couple of differences here.

We've now got a first and last.

Now these store, the indices of the first and the last items in the list while the search item might be found.

And lastly, we've got our flag.

Now, the Flag start as false because we've not found it yet.

And it will change the true if the item has been found.

So at this point we're finding the middle item to the midpoint between the first and the last.

How do you do that? We add the first and last values together and calculate the flow division of the total by two.

Now, when we do this it automatically gives us the middle left item.

So when we spoke about the binary search previously, we said, if you've got a odd set of odd number of items, the list, the middle items, easy to find if it was an even number of items in the list, is going to the middle left item.

Plus, that's the reason why because we're using the function here.

What's the condition of the selection statement? Compare the item at the midpoint to the item that you're searching for.

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

what is the condition of the selection statement? Otherwise, check whether the item at the midpoint is lower than the search item.

Focus on the items that are larger than the midpoint by setting the first index to just after the midpoint index.

Because we know that the item is not the midpoint.

It's going to be one more than the midpoint.

So we're setting our index there.

Otherwise, the item at the midpoint must be higher than the such item.

Focus on the items that are smaller than the midpoint by setting the last index to just before the midpoint index.

So we're going just before the midpoint 'cause we've already searched the midpoint and we know that's not the item.

So we're going to go to the items that are before it.

Statements are placed inside the loop.

So that the process is repeated with the number of items between first and last being halved at each iteration.

Iteration just means that we're repeating it each time.

Iterating through the algorithm, repeating the steps of the algorithm.

And it occurs only with the instructions or the code that's within the while loop.

What is The condition of the while loop? Have an attempt.

Try writing your answers down.

Okay.

Let's see.

So we're repeating while there are still items between the first and the last on the search item has not been found.

So we're going to keep repeating this until we've got items in the list and until we find the item that we're looking for.

But once again, here, we're returning and we're returning the index where the search item was found on the same question again.

What value is returned if the search item has not been found? What do you think? Okay.

The initial value of minus one indicates that the item has not been found.

The exact same with the linear search.

TasK three "code for binary search".

The final task is based on the binary search algorithm written in Python.

Pause the video to complete your task.

Task three "code for binary search".

Using the worksheet complete task three.

Resume once you're finished.

Summary of linear search on binary search.

So we looked at the linear search by research individually in the previous lessons.

And this lesson has been a comparison.

So we now know the linear search can be used if the data is audit or an audit.

But the binary search can only be used, if the data is ordered.

The number of comparisons we know that the binary search, each time you you're looking for an item, the data is halved each time.

And if you double the list, it's just one more iteration.

However, with the linear search, we're looking through every single item.

If we double the list the number of comparisons are also going to double.

And you've just seen the Python code for both searches.

So you can see that the algorithm for the linear search was a lot simpler to write as opposed to the algorithm for the binary search.

Thank you very much for joining me on this lesson.

You can share your work with Oak National.

You can do that using Twitter, Facebook, or Instagram targeting @Oak National and hashtag learn with Oak.

Looking forward to you joining me on the next lesson.

So thank you very much for your time today and hopefully I'll see you on the next lesson.

Goodbye.