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

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

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

Guess the number.

You are guessing a number that someone is thinking of between one and 15.

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

For the first attempt, you guess eight, and the person replies, "Lower." Looking at the table below, we can see the 50 numbers, and we can see our guess.

What number will you guess next? And what would be the maximum number of guesses for 15 numbers? Have a go.

Write your answers down.

Okay.

So the next guess that I would make would be the number four.

Did you get that right? Why? Because first, I guessed eight, which was in the middle of them numbers.

I know it's lower, so therefore, I can eliminate all the way from eight to 15.

And then, between one and seven, four is in the middle, the midpoint.

The second question, what would be the maximum number of guesses? Did you get four? Four would be the answer because first, we've guessed eight, which was in the middle of one to 15.

Then we've guessed four, which is in the middle of one to seven.

And then, it can either go less than four, more than four, or it could be four, but we're looking at the maximum here.

So then, let's imagine it's less than four.

So we're going to guess the number two.

And then, if they tell us it's less, more, or equal to, then we could get to the correct answer.

So therefore, the answer there would have been four.

The whole purpose of this data was to get you thinking about a logical way of finding numbers.

Before we cover the linear search, and now, we're going to move on to looking at the binary search.

In this lesson, you will describe how binary search is used to find the position of an item in the list of items, perform a binary search to find the position of an item in the list, and identify when binary search can and cannot be carried out.

Using feedback to find the number.

The most efficient way to find a number based on feedback, correct, higher, or lower, is to check the middle number each time.

If the middle number is correct, you are done.

So we've found it, algorithm over.

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

So if it was lower, we can ignore all the numbers from eight all the way up until 15.

With the number four, if it's lower, we can ignore four all the way up to seven.

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

So four's highlighted there.

If it is higher, we can ignore one all the way till four.

So we're left with five, six, and seven.

You can repeat this process with the remaining numbers until you find the correct number.

This is how a binary search works.

Binary search.

Binary search is a much more efficient way of searching through a list of items than a linear search.

However, you can only use a binary search algorithm if the data is ordered from smallest to largest.

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

Binary search.

Each number is hidden under a cup.

The cups are arranged in order with the lowest value on the left, so under cup one, and the highest number on the right, so under cup nine.

The number to find is 68.

So our first step here, we're taking an ordered list of data and an item that is being searched for, the search item, which in this case is the number 68.

Maintain a range of items where the search item might be found.

Initially, set the range to the entire list.

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

So from cup one to cup nine, that's our range, and we're looking for the number 68.

Find the item in the middle of the range, the midpoint item, so cup five, in this case.

Compare the midpoint item to the item that you're searching for.

So we're comparing 52 with 68.

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

So 52 is less than 68, so we've changed our range from one to nine to six to nine.

The items are arranged in order.

So the search item cannot be found before the midpoint.

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

So in this case, we've got an even number of items. When we've got an odd number, it's really simple to find the middle item.

However, in this case and in cases when you do have an even number, you always go to the middle-left item, or in most binary search algorithms, that's how it's specified.

So the midpoint here would be cup number seven.

Compare the midpoint item to the item you're searching for.

So we're comparing 68 with 73.

If the midpoint item is greater than the search item change the range to focus on the items before the midpoint.

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

So here, we were looking for 68.

The midpoint here is 73.

So it's still going to be after there.

So therefore, it's going to be before that point, if it is in the list.

Find the item in the middle of the range.

If there is only one item, select this item.

So we're only left with one cup.

Compare the midpoint item to the item you're searching for.

So we're looking for 68.

We've found 68.

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

Algorithm for binary search.

Step one, take an ordered list of data on an item that is being searched for.

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

Initially, set the range to be the entire list.

Step three, repeat the following steps until you find the item that you're searching for or that are normal items to check.

So the range is empty, and the item is not within the range.

So within step three, we're going to repeat these steps: A, find the item in the middle of the range, so the midpoint; B, compare the midpoint item to the item that you're searching for; C, if the midpoint item is equal to the search item, stop searching; D, if the midpoint item is less than the search item, change the range to focus on the items after the midpoint; and lastly, if the midpoint item is greater than the search item, change the range to focus on the items before the midpoint.

So they're the steps for the algorithm for binary search.

Task one, searching ordered cards.

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

Take 10 cards, and choose a card to search for.

Put the cards in order from lowest to highest.

Place eight 8/10 cards face down in a single row without looking at them.

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

Rules.

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

Pause the video to complete your task.

Task one, searching ordered cards.

Using the worksheet, complete task one.

Resume once you have finished.

Performance of binary search.

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 that if you had 1,000 items to search through, it would take at most 10 comparisons for a binary search to find them.

If you doubled the number to 2,000 items, it would only increase the greatest possible number of comparisons by one task.

Task two, performing a binary search.

You're now going to perform a binary search on given scenarios.

Scenario one involves searching for an instrument, and scenario two involves searching for an animal where you have to consider best case and worst case scenarios.

Pause the video to complete your task.

Task two, performing a binary search.

Using the worksheet, complete task two.

The two scenarios are searching for an instrument, best case and worst case.

Resume once you have finished.

Ordered and unordered data.

When faced with a data searching problem, you'll either have to deal with ordered or unordered sequences of items. Does data need to be in a sequence for you to perform a linear search on it? Can you perform a binary search on a list of unsorted items? And why are phone books and directories sorted? Write down your answers? Okay.

So with the linear search, it doesn't make a difference if the data is ordered or unordered.

For a binary search, the list of items has to be sorted.

We cannot perform a binary search on a list of unsorted items and phone books and directories.

So why did you think they were sorted? Because it's just easier for us to navigate and find that information.

So if it's alphabetical, we can look through it, find that bit of information.

However, if it was unsorted, it would take us a very long time to find the information that we were looking for.

Thank you very much for joining me on this binary search lesson.

I hope you've got a better insight in terms of the searching algorithms, and you can share your work with us at OakNational.

Please, do ask a parent or carer, and you can do that using Instagram, Facebook, or Twitter tagging @Oaknational and #LearnwithOak.

Thank you for joining me today, and hopefully, I'll see you on the next lesson.

Goodbye.