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 binary search algorithm.

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

Welcome to today's lesson from the unit Searching and Sorting Algorithms. This lesson is called Binary Search, and by the end of today's lesson, you'll be able to identify when a binary search can be used and perform its steps on a set of data.

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

Binary search.

Binary search, an algorithm to search for an item in a sorted data set.

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

Ordered list.

Ordered list, a list of items where the values are either in ascending or descending order.

Look out for these key words throughout today's lesson.

Today's lesson is split into two parts.

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

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

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

You are guessing the number that someone is thinking of between 1 and 15.

The only feedback you get from the person is correct, higher or lower.

What would be your first guess? Maybe pause the video whilst you have a think.

Ah, Jun says, "I would start in the middle, so the number 8." That's a really good idea, Jun.

For the first attempt, you guess eight and the person replies lower.

What number will you guess next? What would be the maximum number of guesses needed for 15 numbers? Maybe pause the video whilst you have a think.

Jun says, "I would go for the middle item again, so the number 4.

The maximum number of guesses for 15 numbers would be four guesses." The most efficient way to find a number based on the feedback correct, higher or lower, is to check the middle number each time.

If the middle number is correct, then you're done.

If the middle number gets the feedback lower, you can ignore all the numbers after it.

If the middle number gets the feedback higher, you can ignore all the numbers before it.

Binary search works in exactly this way, and is a much more efficient way of searching through a list of items compared to a linear search.

However, you can only use a binary search algorithm if the data is ordered or sorted.

If the data you have is unordered, you must either use a linear search algorithm or sort the data before you perform the binary search.

Time to check your understanding.

True or false? A binary search can be used on any data.

Pause the video whilst you have a think.

Did you select false? Well done.

You can only use a binary search algorithm if the data is ordered.

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

Two, maintain a range of items where the search item might be found.

Initially, set the range to be the entire list.

Three, find the item in the middle of the range.

This is called the midpoint item.

Four, compare the midpoint item to the item you are searching for.

Five, if the midpoint item is less than the search item, change the range to focus on the items after the midpoint.

Six, if the midpoint item is greater than the search item, change the range to focus on the items before the midpoint.

Seven, if the item at the midpoint is equal to the search item, then stop searching.

Each number is hidden under a cup.

The cups are arranged in order with the lowest value on the left, and our search item or the number to find is 68.

So our first step is to take an ordered list of data and an item that is being searched for, the search item, which in this case is 68.

We maintain the range of items where the search item may be found.

Initially set the range to the entire list.

The range is specified through the indices of the first and last items in the range.

So we have nine cups at the start of this search.

Find the item in the middle of the range, the midpoint item.

So in this case, that's going to be cup five.

The value in cup five is 52.

We compare the midpoint item to the item we're searching for, so 52 compared to 68.

If the midpoint item is less than the search item, which it is in this case, we change the range to focus on the items after the midpoint.

So you can see cups one to five have now been greyed out and will be ignored.

The items are arranged in order, so the search item cannot be found before the midpoint.

We then find the item in the middle of the range, the midpoint item again.

If there is an even number of items, then you select the middle left item.

So in this case, cup seven.

Cup seven contains the value 73.

So we compare the midpoint item to the item we're searching for, 73 compared to 68.

If the midpoint item is greater than the search item, then we're going to change the range to focus on the items before the midpoint.

So you can now see we've greyed out the cups to the right-hand side of the midpoint.

The items are arranged in order, so the search item cannot be found after the midpoint.

Find the item in the middle of the range.

So we've now only got one item in our range, so the middle is that item.

Okay? So there's only one item left.

So we're going to select this item and that holds the value 68.

We compare the midpoint item to the item we're searching for.

If the item at the midpoint is equal to the search item, then we stop searching.

Time to check your understanding.

Put these binary search algorithm steps 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 the first step is to take an ordered list of data and an item that is being searched for, the search item.

The second step is to maintain a range of items where the search item might be found.

The third step is to find the item in the middle of the range, the midpoint item.

Step four, compare the midpoint item to the item you're searching for.

Step five, if the midpoint item is less than the search item, change the range to focus on the items after the midpoint.

Step six, if the midpoint item is greater than the search item, change the range to focus on the items before the midpoint.

If you have five and six the other way round, that's absolutely fine.

And then lastly, seven, if the item at the midpoint 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 binary search was used to find the four of spades card in this list of cards.

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

How did you get on? Did you manage to describe the binary search steps? Well done.

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

The binary search will start with the midpoint in the list, which is the five of spades.

It will compare this item to the search item, which is the four of spades.

The midpoint item is greater than the search item, so the range to focus on is changed to the items before the midpoint.

The midpoint of the next range is found, which is the three of spades, and compared to the search item.

As the midpoint item is less than the search item, the range to focus on is changed to the items after the midpoint.

Now, the remaining card and midpoint is the same card, which is the four of spades, which is also equal to the search term, so the algorithm stops.

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

So we've described how binary search finds an item.

Let's move on to perform a binary search on some data.

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

Take eight cards and choose a card to search for.

Put the cards in order from lowest to highest.

Place the cards face down in a single row without looking at them, but remember to maintain the order.

Perform a binary search for your chosen card.

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

Binary search is a very powerful algorithm because of how fast it is.

In the previous examples, you saw that with each comparison, the algorithm eliminates half of the data.

That means if you had a thousand items to search through, it would take at most 10 comparisons for a binary search to find an item.

If you doubled that number to 2,000 items, it would only increase the most number of comparisons by one.

That's quite amazing.

Time to check your understanding.

Which value card is at the first midpoint calculated by the binary search algorithm? Pause the video whilst you have a think.

Did you have the seven of spades? Well done.

The seven of spades is the midpoint item in this set of cards.

You've been provided with some cards that are in the following order.

Why would you not use a binary search for this data? Is it A, the data is not a list of numbers? B, the data is not sorted in an ascending or descending order.

Or C, there is not enough data.

Pause the video whilst you have a think.

Did you select B? Well done.

I knew you'd get this one right.

The data is not sorted.

And remember, in order to conduct a binary search, the data must be sorted first.

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

Jun has created a programme that stores all of the instruments that a music shop currently sells or hires to customers.

A sample of data is shown in Figure 1.

So we have a list that contains the item banjo, cello, drums, flute, guitar, harp, oboe, piano, and violin.

For part one, list the instruments that will be compared to the instrument harp when performing a binary search on the data shown in Figure 1.

For part two, list the instruments that will be compared to the instrument flute when performing a binary search on the data shown in Figure 1 And then for part three, list the instruments that will be compared to the instrument trumpet when performing a binary search on the data shown in Figure 1.

For part four, describe the stages of a binary search to find the instrument drums when performing a binary search on the data shown in Figure 1.

Pause the video whilst you complete the tasks.

How did you get on? Did you manage to perform a binary search on the data? Great work.

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

So for part one, you were asked to list the instruments that will be compared to the instrument harp when performing a binary search on the data shown in Figure 1.

The first item would be guitar 'cause that's the midpoint.

The second item would be oboe 'cause that would be the next midpoint.

And then the final item would be harp.

For part two, you were asked to list the instruments that will be compared to the instrument flute when performing a binary search on the data shown in Figure 1.

Again, the first item would be guitar.

But this time because the search item is flute, which comes before guitar, our focus is shifted to the left hand side of the list.

So the midpoint is then cello, then drums, and then flute.

So we've got four items that would be compared there.

And then for part three, you were asked to list the instruments that will be compared to the instrument trumpet when performing a binary search on the data shown in Figure 1.

Trumpet isn't in the list, so the search items that would be compared would be guitar, oboe, piano, and violin.

And then the algorithm would return that the search item had not been found.

For part four, you were asked to describe the stages of a binary search to find the instrument drums when performing a binary search on the data shown in Figure 1 A, compare drums to guitar.

B, drums is less than guitar, so discard the items on the right and search the left side.

C, compare drums to cello.

D, drums is greater than cello, so discard the items on the left and take the right side.

E, compare drums to drums, and the search item has been found.

Did you have similar steps? Remember, if you need to pause the video and add some extra detail to your answer, you can do that now.

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

Another sample of data is shown in Figure 2.

So this time, we've got some animals.

So we have crow, deer, eagle, horse, lion, moose, rhino, tiger, and zebra.

For part one, which animal would you search for to incur the best case scenario in Figure 2? For part two, how many comparisons would need to be made in the best case scenario in Figure 2? For part three, which animal could you search for to incur the worst case scenario in Figure 2? And for part four, how many comparisons would need to be made in the worst case scenario in Figure 2? Pause the video here whilst you complete the tasks.

How did you get on? Did you manage to perform a binary search and look at the best and worst case scenarios? Well done.

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

For part one, you were asked, which animal would you search for to incur the best case scenario in Figure 2? That would be the lion because that's the midpoint item and the first item that would be looked at.

For part two, how many comparisons would need to be made in the best case scenario? That's one.

For part three, which animal could you search for to incur the worst case scenario in Figure 2? So that would either be horse or zebra or any other animal that is not in the list.

How many comparisons would need to be made in the worst case scenario? That would be four comparisons.

Okay, we've come to the end of today's lesson, binary search.

You've done a fantastic job, so well done.

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

Binary search is an algorithm which can be used to search for an item in a sorted data set.

It discards half of the remaining data with each comparison and repeats the process until the item is found or until the dataset is exhausted.

On average, binary search can locate an item in a list in less time than a linear search.

If the data that you have is unordered, you must either use a linear search algorithm or sort the data first.

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

Bye.