- [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're 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 eight breakfast cereals, and they each have an index of zero to seven.
We've set a left pointer over the first item, Coco Pops, with an index of zero
and a right pointer over the last item, Weetabix, with an index of seven.
We then need to calculate a midpoint.
This is done by adding the left pointer, zero, to the right pointer, seven.
The answer is seven, which we now divide by two to 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 seven divided by two is three, and that's our midpoint.
So we're now going to check the item that is index three 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 it can't be one of those.
The left pointer now becomes the midpoint plus one.
We can now repeat the algorithm.
The left pointer, four, plus the right pointer, seven, equals eleven, divided by two is five.
So the midpoint is five.
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 midpointer minus one, which is four.
When the left and right pointers are the same value,
the item we are 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 the binary search, we perform just three.
As the lists get bigger, on average,
the time it takes a binary search to find the item will be lower than the 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 specification at GCSE requires you to know the mechanics of an algorithm.
You should understand the advantages and disadvantages of
using one algorithm over another to solve the same problem.
However, at GCSE level, you're not going to be expected to remember the code line for line for a given algorithm.
In the rest of this video, we're going to walk through an example of this algorithm step by step.
So we start by initialising some states for our variables, flags and pointers.
So we're going to set found to false, our left pointer to zero,
and our right pointer to the length of the list minus one.
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 equals to the right pointer,
then calculate a midpoint, mid equals left plus right DIV two.
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.
So just before we end this video,
we're going to have a look and compare the two GCSE searching algorithms that you need to know about,
the linear search and the binary search.
If you've not watched the video on the linear search yet,
you should go back and watch that now before watching the rest of this video.
So on the left, we have our binary search and on the right, our linear search.
So with a binary search, the items have to be in order for the algorithm to work,
which means if they're not in order,
you first have to perform some form of sorting algorithm before you could even start a binary search.
With a linear search, the items do not need to be in any order at all,
so it can start immediately with an unsorted list.
With a binary search, we start with the middle item,
whereas with a linear search, we start with the first item.
With a binary search, we half the set of items to search after each comparison
until the item is found or there's no more items to check.
Whereas with the linear search, we search each item in sequence
until the item is found or there's no more items to check.
With a binary search, new items must be added in the correct position
in order to maintain the fact that the items need to be in order, and this can be slow.
With a linear search, new items can simply be added to the end, which is nice and quick.
However, binary searches are much faster for large sets of numbers or data
because with every comparison, it halves the amount of remaining items you need to search for.
Linear searches are suitable but really only for a small number of items.
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)