Lesson hub

## Can't find the answer? Try online tutoring

We have the UK’s best selection of online tutors, when and for how long you need them.

Getting 1-on-1 support is cheaper than you might think.

### Participating users

Welcome to our free-to-use Q&A hub, where students post questions and get help from other students and tutors.

You can ask your own question or look at similar Computing questions.

This is an example of a search algorithm.

How you can search through a list depends upon whether the list is sorted or not.  The only way to search through a completely random list is to do so one by one, starting at the beginning and ending at the found position.

The list of pictures is actually ordered because the pictures start as a series with the eggs in place and ends with a series with the eggs gone.  This means you can use a binary search.

First, let us assume we have a function to examine the pictures and determine whether the eggs are in place. Let’s call it FUNCTeggs(index) and assume that it returns a value of TRUE if the eggs are present and FALSE if they are not. In practice this would be a complicated bit of software and might take some time to run, so we need to call it as few times as possible.

We will need some other variables as well:

upperbound – the upper number in the binary search

lowerbound – the lower number in the binary search

picnum – the number of the picture we are looking at

pic1, pic2 – the results of the search for two consecutive pictures.

We are looking for two different results for two consecutive pictures, one with eggs, the next, without eggs. This is found using “pic1 XOR (exclusive OR) pic2” which is only TRUE if the two pictures are different.

If unsuccessful we need to decide if we need to go forward along the list or to backtrack. (this is why we need the list ordered)

This is decided by “pic1 AND pic2”, if both are TRUE we need to go forwards down the list, otherwise we need to go backwards towards the start.  This is done by changing the upper or lower boundary.

The “picnum>=287” terminates the loop in the event of a null search. You might want to confirm this condition.

upperbound ←288

lowerbound ← 1

BEGIN LOOP

picnum ← INT((upperbound+lowerbound)/2)

pic1 ← FUNCTeggs(picnum)

pic2 ← FUNCTeggs(picnum+1)

IF pic1 XOR pic2 THEN exit loop

IF picnum >= 287 THEN exit loop

IF pic1 AND pic2 THEN lowerbound ← picnum ELSE upperbound ← picnum

CONTINUE LOOP

A simple search, if the FUNCTeggs() function takes 5 minutes, might take up to 24 hours to fullfil (288 calls).  With this binary search the FUNCTeggs() will be called a maximum of 18 times which would mean a maximum of an hour and a half. This routine will call FUNCTeggs() multiple times for the same picture during a search so a method of producing a trail of results is needed to avoid this.

On a successful exit “picnum” contains the number of the last picture that contains the eggs.

A naive approach would be to just iterate through all the pictures and see when the eggs are gone... what would be a quicker way? Is there any way we can avoid checking some of the pictures?