- [Craig] In this video, we're going to consider the binary search,
which is often a more efficient way of searching compared to a linear search.
(uplifting piano jingle)
So, before we get into working through an example of the binary search, let's just overview some of its features.
With a binary search, we calculate a midpoint in the data set
and we check if the item at that midpoint is the item we're looking for.
If it's not, if it's lower than the midpoint then we repeat the process on the left half of the data set.
Otherwise, we repeat it on the right half of the data set.
A binary search requires the data to already be in order of a key field,
and it's more efficient than a linear search on average.
With a binary search, instead of starting at the beginning of a data set
and checking each item until the one that you're looking for has been found,
you calculate a midpoint in the data set and check if that's the item to be found first.
If it's not and the item you're looking for is lower than the item at the midpoint
then you can disregard all the items to the right of the midpoint
and repeat the algorithm only on the left half of the list.
In a similar way, if the item you are looking for is greater than the item at the midpoint,
you can disregard all the items to the left of the midpoint and repeat the algorithm only on the right half of the list.
In doing so, you are disregarding half of the items in the list each time.
However, the binary search requires the data to be in order for it to work,
but it's much more efficient than a linear search on average.
So, let's look at a typical example.
Here, we've got a data set of 8 breakfast cereals, and they each have an index of 0 to 7.
We've set a left pointer over the first item, Coco Pops, with an index of 0,
and a right pointer over the last item, Weetabix, with an index of 7.
We then need to calculate a midpoint.
This is done by adding the left pointer, 0, to the right pointer, 7.
The answer is 7, which we now divide by 2 to the find the middle.
We need the answer to be a whole number, so instead of a regular division,
we can use what is called an integer division instead.
With integer division, only a whole number is returned with no rounding,
so 7 divided by 2 is 3, and that's our midpoint.
So, we're now going to check the item that's at index 3 to see if it's the one we're looking for.
So, let's assume we're looking for Rice Krispies.
Well, Fruit 'n' Fibre is not Rice Krispies, it's greater, so we can disregard all items to the left.
We know if can't be one of those.
The left pointer now becomes the midpoint plus 1.
We can now repeat the algorithm.
The left pointer, 4, plus the right pointer, 7, equals 11, divided by 2 is 5, so the midpoint is 5.
Is Special K the item we're looking for?
No, it is greater, so we can disregard all the items to the right.
The right pointer now becomes the mid pointer minus 1, which is 4.
When the left and right pointers are the same value, the item we're looking for is either at the pointer or it's not in the list.
With a linear search, by starting at the first item in the list
and checking every item in the list until we find the one we're looking for,
we would have performed five checks.
With a binary search, we performed just three.
As the lists get bigger, on average,
the time it takes a binary search to find the item will be lower than a linear search,
so the binary search is generally considered a better algorithm,
providing the order of the items in the list can be maintained.
This is not always desirable given what the main program is trying to achieve.
Of course, there are some situations where the binary search is not better,
and you might be able to spot them.
For example, if the item we're looking for is the first one in the list.
However, this is not usually the case, and certainly not with larger data sets.
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 are not required to remember the code for these algorithms.
In the rest of this video, we will work through the pseudocode of the algorithm.
While it is important and you need to be able to spot this code, don't get worried about remembering it line for line.
So, we start by initialising some states for our variable, flags and pointers.
So, we're going to set found to false, our left pointer to 0 and our right pointer to the length of the list minus 1.
And we're going to enter a WHILE loop,
and we're going to say while the found Boolean flag is false and the left pointer is less than or equal to the right pointer,
then calculate a midpoint,
mid = (left + right) DIV 2
If the item at the midpoint is the item to find, then we can set the value of found to true.
Else if we haven't, then check to see if the item we're looking for is greater than our midpoint item.
If it is, then increment the left pointer.
If it's not, then decrement the right pointer.
We know that algorithms are some of the hardest parts of any computer science specification,
so we have 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)