D1 Algorithms - Binary search PhysicsAndMathsTutor.

com

1. Use the binary search algorithm to try to locate the name NIGEL in the following alphabetical
list. Clearly indicate how you chose your pivots and which part of the list is being rejected at
each stage.

1. Bhavika
2. Clive
3. Elizabeth
4. John
5. Mark
6. Nicky
7. Preety
8. Steve
9. Trevor
10. Verity
(Total 4 marks)

2. 650 431 245 643 455 134 710 234 162 452

(a) The list of numbers above is to be sorted into descending order. Perform a Quick Sort to
obtain the sorted list, giving the state of the list after each pass, indicating the pivot
elements.
(5)

The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold
in one metre lengths.

(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be
cut from the minimum number of one metre lengths. (You should ignore wastage due to
cutting.)
(4)

(c) Determine whether your solution to part (b) is optimal. Give a reason for your answer.
(2)
(Total 11 marks)

Edexcel Internal Review 1

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

3.
Hajra Vicky Leisham Alice Nicky June Sharon Tom Paul
(H) (V) (L) (A) (N) (J) (S) (T) (P)

The table shows the names of nine people.

(a) Use a quick sort to produce the list of names in ascending alphabetical order.

You must make your pivots clear.

(4)

(b) Use the binary search algorithm on your list to locate the name Paul.
(4)
(Total 8 marks)

4. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are

0.6, 4.0, 2.5, 3.2, 0.5, 2.6, 0.4, 0.3, 4.0 and 1.0

Guttering is sold in 4 m lengths.

(a) Carry out a quick sort to produce a list of the lengths needed in descending order. You
should show the result of each pass and identify your pivots clearly.
(5)

(b) Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the
total number of 4 m lengths needed.
(4)

(c) Does the answer to part (b) use the minimum number of 4 m lengths? You must justify
your answer.
(2)
(Total 11 marks)

Edexcel Internal Review 2

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

5. Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan

(a) Use the quick sort algorithm to sort the above list into alphabetical order.
(5)

(b) Use the binary search algorithm to locate the name Louis.
(4)
(Total 9 marks)

6. Max Lauren John Hannah Kieran Tara Richard Imogen

(a) Use a quick sort to produce a list of these names in ascending alphabetical order. You
must make your pivots clear.
(5)

(b) Use the binary search algorithm on your list from part (a) to try to locate the name
‘Hugo’.
(4)
(Total 9 marks)

7. Use the binary search algorithm to try to locate the name NIGEL in the following alphabetical
list. Clearly indicate how you chose your pivots and which part of the list is being rejected at
each stage.

1. Bhavika
2. Clive
3. Elizabeth
4. John
5. Mark
6. Nicky
7. Preety
8. Steve
9. Trevor
10. Verity
(Total 4 marks)

Edexcel Internal Review 3

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

8. 45, 56, 37, 79, 46, 18, 90, 81, 51

(a) Using the quick sort algorithm, perform one complete iteration towards sorting these
numbers into ascending order.
(2)

(b) Using the bubble sort algorithm, perform one complete pass towards sorting the original
list into descending order.
(2)

Another list of numbers, in ascending order, is

7, 23, 31, 37, 41, 44, 50, 62, 71, 73, 94

(c) Use the binary search algorithm to locate the number 73 in this list.
(4)
(Total 8 marks)

9.
1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth

A binary search is to be performed on the names in the list above to locate the name Newcastle.

(a) Explain why a binary search cannot be performed with the list in its present form.
(1)

(b) Using an appropriate algorithm, alter the list so that a binary search can be performed.
State the name of the algorithm you use.
(4)

(c) Use the binary search algorithm on your new list to locate the name Newcastle.
(4)
(Total 9 marks)

Edexcel Internal Review 4

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

10. The following list gives the names of some students who have represented Britain in the
International Mathematics Olympiad.

Roper (R), Palmer (P), Boase (B), Young (Y), Thomas (T), Kenney (K), Morris (M),
Halliwell (H), Wicker (W), Garesalingam (G).

(a) Use the quick sort algorithm to sort the names above into alphabetical order.
(5)

(b) Use the binary search algorithm to locate the name Kenney.
(4)
(Total 9 marks)

Edexcel Internal Review 5

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

1 + 10 
1.  2  = 6 Nicky M1
 
reject top of list
 7 + 10 
 2  = 9 Trevor A1
 
reject bottom of list
7 + 8
 2  = 8 Steve A1
 
reject bottom of list
[7] = 7 Preety A1 4
reject
Nigel not in list
[4]

2. (a) E.g:
650 431 245 643 455 710 234 162 452 134 M1
650 643 710 455 431 245 234 162 452 134 A1
650 710 643 455 431 245 452 234 162 134 A1 ft
710 650 643 455 431 452 245 234 162 134 A1 ft
710 650 643 455 452 431 245 234 162 134 A1

(b) Bin 1 710 + 245 Bin 3 643 + 162 + 134 Bin 5 431 M1A1
Bin 2 650 + 234 Bin 4 455 + 452 A1A1(ft) 4

4116
(c) = 4.116 5 bins needed optimal M1A1(ft) 2
1000
[11]

Edexcel Internal Review 6

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

3. (a)

H V L A N J S T P (N) M1
H L A J N V S T P (A, T) A1
A H L J N S P T V (L, P) A1 ft
A H J L N P S T V (J)
A H J L N P S T V A1 cso 4

Note
1M1: quick sort, pivots, p, chosen and two sublists one <p one >p.
1A1: first pass correct and next pivots chosen correctly/consistently.
2A1ft: second pass correct, next pivots correctly/consistently chosen.
3A1: all correct, cso.

1 + 9 
(b) 1st choice  = 5 Nicky, reject 1 – 5 M1 A1
 2 
6 + 9
2nd choice  = [7.5
= ] 8 Tom, reject 8 – 9 A1
 2 
6 + 7
3rd choice  = [6.5
= ] 7 Sharon, reject 7
 2 
4th choice 6 Paul name found A1 cso 4

Note
1M1: binary search on what they think is a alphabetical list, choosing
pivot, rejecting half list.
1A1: first pass correct, condone ‘sticky’ pivot here, bod generous
2A1: second pass correct, pivot rejected.
3A1: cso.
Note: If incorrect list in (a) mark (b) as a misread.

Alternative solutions
Middle right
H V L A N J S T P (N) M1
H L A J N V S T P (A T) A1
A H L J N S P T V (L P) A1ft
A H J L N P S T V (J)
A H J L N P S T V A1cso

list sorted

Edexcel Internal Review 7

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

Middle left
H V L A N J S T P (N) M1
H L A J N V S T P (L S) A1
H A J L N P S V T (A V) A1ft
A H J L N P S T V (H)
A H J L N P S T V A1cso

First
H V L A N J S T P (H) M1
A H V L N J S T P (V) A1
A H L N J S T P V (L)
A H J L N S T P V (N) A1ft
A H J L N S T P V (S)
A H J L N P S T V A1cso
[8]

4. (a)
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 2.6
4.0 3.2 4.0 2.6 0.6 2.5 0.5 0.4 0.3 1.0 3.2 0.4 M1
4.0 4.0 3.2 2.6 0.6 2.5 0.5 1.0 0.4 0.3 4.0 0.5 A1
4.0 4.0 3.2 2.6 0.6 2.5 1.0 0.5 0.4 0.3 2.5 A1ft
4.0 4.0 3.2 2.6 2.5 0.6 1.0 0.5 0.4 0.3 1.0 A1ft
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3 A1 cso 5

Notes
1M1 Pivot, p, chosen. List sorted, >p, p.
<p or <p, p, >p. If only choosing 1
pivot per iteration M1 only
1A1 1st pass correct and chosen next two
pivots correctly for sublists >1
2A1ft 2nd pass correct and chosen next two
pivots correctly for sublists >1
3A1ft 3rd pass correct and next pivot for
sublist >1 chosen correctly.
4A1 cso.

Edexcel Internal Review 8

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

Misread in part (a)

• If they have misread a number at
the start of part (a), so genuinely
miscopied and got for example 0.1
instead of 1.0 then mark the whole
question as a misread – removing the
last two A or B marks earned. This
gives a maximum total of 9.
• If they misread their own numbers
during the course of part (a) then count
it as an error in part (a) but mark parts
(b) and (c) as a misread. So they would
lose marks in (a) for the error and then
the last two A or B marks earned in (b)
and (c) – giving a maximum of 8 or maybe
7 marks depending on how many marks
they lose in (a).
The most popular misread is the one listed above – where
1.0 has changed to 0.1 giving
4.0 4.0 3.2 2.6 2.5 0.6 0.5 0.4 0.3 0.1 at the end of (a) for
this one (b) and (c)
are:

(b) Length 1: 4
Length 2: 4
Length 3: 3.2 0.6 left column & 1.0 in place M1
Length 4: 2.6 1.0 0.4 0.6 & 0.5 A1
Length 5: 2.5 0.5 0.3 0.4 A1
All correct (c.s.o) A1 4
Note
Length 1: 4
Length 2: 4
Length 3: 3.2 0.6 0.1
Length 4: 2.6 0.5 0.4 0.3
Length 5: 2.5

Edexcel Internal Review 9

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

(c) 19.1/4 = 4.775 so 5 lengths needed, accept

total is 19.1m, or refer to 0.9 ‘spare . B1
Yes, the answer to (b) does use the minimum
number of bins. DB1 2
Note
18.2/4 = 4.55 so 5 bins, or total is 18.2 or 1.8 ‘spare’
Yes answer in (b) uses the minimum number of bins.

Alternate
Choosing middle left
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.5)
0.6 4.0 2.5 3.2 2.6 4.0 1.0 0.5 0.4 0.3 (pivots 3.2, 0.4)
4.0 4.0 3.2 0.6 2.5 2.6 1.0 0.5 0.4 0.3 (pivots 4.0, 2.5)
4.0 4.0 3.2 2.6 2.5 0.6 1.0 0.5 0.4 0.3 (pivot 0.6)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3

Choosing first
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
4.0 2.5 3.2 2.6 4.0 1.0 0.6 0.5 0.4 0.3 (pivots 4.0, 0.5)
4.0 2.5 3.2 2.6 4.0 1.0 0.6 0.5 0.4 0.3 (pivots 2.5, 0.4)
4.0 3.2 2.6 4.0 2.5 1.0 0.6 0.5 0.4 0.3 (pivot 3.2)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3

OR (alternate choosing first)

0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
4.0 2.5 3.2 2.6 4.0 1.0 0.6 0.5 0.4 0.3 (pivots 4.0, 0.5)
4.0 4.0 2.5 3.2 2.6 1.0 0.6 0.5 0.4 0.3 (pivots 2.5, 0.4)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3 (pivots 3.2)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3

Sorting into ASCENDING order (full marks if then reversed, otherwise MISREAD)

Middle left
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.5)
0.4 0.3 0.5 0.6 4.0 2.5 3.2 2.6 4.0 1.0 (pivots 0.4, 3.2)
0.3 0.4 0.5 0.6 2.5 2.6 1.0 3.2 4.0 4.0 (pivots 2.5, 4.0)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0 (pivot 0.6)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0

Edexcel Internal Review 10

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

Middle right
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 2.6)
0.6 2.5 0.5 0.4 0.3 1.0 2.6 4.0 3.2 4.0 (pivots 0.4, 3.2)
0.3 0.4 0.6 2.5 0.5 1.0 2.6 3.2 4.0 4.0 (pivots 0.5, 4.0)
0.3 0.4 0.5 0.6 2.5 1.0 2.6 3.2 4.0 4.0 (pivot 2.5)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0 (pivot 1.0)

First (1)
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
0.5 0.4 0.3 0.6 4.0 2.5 3.2 2.6 4.0 1.0 (pivots 0.5, 4.0)
0.4 0.3 0.5 0.6 2.5 3.2 2.6 1.0 4.0 4.0 (pivots 0.4, 2.5)
0.3 0.4 0.5 0.6 1.0 2.5 3.2 2.6 4.0 4.0 (pivot 3.2)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0

First (2)
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
0.5 0.4 0.3 0.6 4.0 2.5 3.2 2.6 4.0 1.0 (pivots 0.5, 4.0)
0.4 0.3 0.5 0.6 2.5 3.2 2.6 1.0 4.0 4.0 (pivots 0.4, 2.5)
0.3 0.4 0.5 0.6 1.0 2.5 3.2 2.6 4.0 4.0 (pivot 3.2)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0
[11]

5. (a)
M J E K H B L P N D B M1 1A1
B M J E K H L P N D H
B E D H M J K L P N DL 2A1ft
B D E H J K L M P N (E) K P
B D E H J K L M N P (J) N 3A1ft
B D E H J K L M N P (M)

Sort completed 4A1 5

Edexcel Internal Review 11

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

Note
1M1: quick sort, pivots, p, identified,
two sublists one <p one >p.
If choosing one pivot only per iteration,
M1 only.
1A1: first pass correct, next pivot(s)
chosen consistently.
2A1ft: second pass correct, next pivot(s)
chosen consistently
3A1ft: third pass correct, next pivot(s)
chosen consistently
4A1: cso List re-written or end statement
made or each element been chosen
as a pivot.

1 + 10 
(b)  2  = 6 Katie reject left M1

 7 + 10 
 2  = 9 Natsuko reject right 1A1

7 + 8
 2  = 8 Miri reject right 2A1ft

7 = Louis name found 3A1 4

Note
1M1: binary search, choosing pivot rejecting
half list.
If using unordered list then M0.
If choosing J M1 ony
1A1: first two passes correct, condone
‘sticky’pivots here, bod.
2A1ft: third pass correct, pivots rejected.
3A1: cso, including success statement.
Special case
If just one letter out of order, award
maximum of M1A1A0A0
[9]

6. (a) e.g.

M L J H K T R I M1
J H I K M L T R A1

Edexcel Internal Review 12

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

H J I K M L R T A1ft
H I J K L M R T A1ft
H I J K L M R T A1cso 5

Note
1M1: quick sort, pivots, p, chosen and two sublists one <p one >p.
If choosing 1 pivot per iteration only M1 only.
1A1: first pass correct and next pivots chosen correctly/consistently.
2A1ft: second pass correct, next pivots correctly/consistently chosen.
3A1ft: third pass correct, next pivots correctly/consistently chosen.
4A1: all correct, cso.

(b) Sort complete.

1 + 8 
1st choice   → 5 Lauren reject right M1 A1
 2 

1 + 4 
2nd choice   → 3 John reject right
 2 

1 + 2 
3rd choice   → 2 Imogen reject right A1ft
 2 

4th choice 1 Hannah reject

List now empty so Hugo not in list A1 4
Note
1M1: binary search, choosing pivot, rejecting half list. If using unsorted
list, M0. Accept choice of K for M1 only.
1A1: first pass correct, condone ‘sticky’pivot here, bod.
2A1ft: second pass correct, pivot rejected.
3A1: cso.
[9]

1 + 10 
7.  2  = 6 Nicky – reject top of list. M1
 
 7 + 10 
 2  = 9 Trevor – reject bottom of list A1
 
7 + 8
 2  = 8 Steve – reject bottom of list A1
 
[7] = 7 Preety – reject A1
Nigel not in list
[4]

8. (a) eg. 45 37 18 46 56 79 90 81 51
or 37 18 45 56 79 46 90 81 51

Edexcel Internal Review 13

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

or 45 37 46 18 51 56 79 90 81 M1A1 2

(b) 56 45 79 46 37 90 81 51 18
or 90 45 56 37 79 46 18 81 51 M1A1 2

1 + 11 
(c)  2  = 6 value 44 discard top M1
 
 7 + 11 
 2  = 9 value 71 discard top A1
 
10 + 11 
 2  = 11 value 94 discard bottom A1
 
list reduces to 10th value. This is 73 so
73 has been located as the 10th value A1 4
[8]

9. (a) The list is not in alphabetical order B1 1

(b) Use of Bubble Sort or Quick Sort M1
e.g.
Bubble sort

G N M Y L B C E S P
B G N M Y L C E P S 1st pass
B C G N M Y L E P S 2nd pass
B C E G N M Y L P S 3rd pass
B C E G L N M Y P S 4th pass
B C E G L M N P Y S 5th pass
B C E G L M N P S Y 6th pass

No more changes
Quick sort

G N M Y L B C E S P
B G N M Y L C E S P 1st pass
B G C E L N M Y S P 2nd pass
B C G E L N M S P Y 3rd pass
B C E G L N M P S Y 4th pass
B C E G L M N P S Y 5th pass
B C E G L M N P S Y 6th pass

No sublists > 2 and no more changes

A1 A1ft
No more changes No sublists > 2 + no more changes A1cso 4

Edexcel Internal Review 14

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

(c) 1 2 3 4 5 6 7 8 9 10
B C E G L M N P S Y
[10 + 1]
= 6 Manchester discard first half of list and pivot M1 A1
2
[7 + 10]
= 9 Southampton discard last half of list and pivot
2
[7 + 8]
=8 Plymouth discard last half of list and pivot A1ft
2
Final term 7 Newcastle ∴ word found at 7 A1cso 4
[9]

10. (a) e.g.

R P B Y T K M H W G
M1
B H G K R P Y T M W A1
B G H K R P M T Y W A1 ft
A1 ft
B G H K M P R T W Y A1 ft
B G H K M P R T W Y

10 + 1 
(b)  2  = 6 Palmer; reject Palmer → Young M1 A1
 
 5 + 1 
 2  = 3 Halliwell; reject Boase → Halliwell A1
 
 4 + 5 
 2  = 5 Morris; reject Morris
 
List reduces to Kenney – name found, search complete A1 4
[9]

Edexcel Internal Review 15

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

1. No Report available for this question.

2. No Report available for this question.

3. This proved a good starter and was well answered by many candidates with around 55% getting
full marks. The quick sort was well handled although some candidates did not choose their
pivots consistently. A few candidates did not select a pivot when they had a two element sublist
in the correct order – often HJ, and a minority sorted the list into reverse alphabetical order. It
was alarming that some candidates only selected one pivot per iteration, so, in effect, just
dealing with one sublist at a time. Candidates must show that they are selecting one pivot, per
sublist, per iteration; that is what makes this algorithm so powerful. A number of candidates did
not have the final list in alphabetical order.
Many candidates in part (b) lost marks for failing to reject the pivot and number of candidates
attempted to use the original, unsorted list. Some, who tried for a more ‘minimalist’ solution,
did not make their pivot choice clear, or the order in which they chose pivots.

4. Many candidates scored at least 8 marks here. In part (a) a minority produced an ascending list
and failed to reverse it. Some candidates did not choose their pivots consistently, swapping
between middle right and middle left pivots. The decimals here caused some problems and even
though the original list was printed in the answer booklet, a surprising number of candidates
initially lost one item or changed one, most commonly 1.0 became 0.1. Some candidates found
only one pivot per row, with some not explicitly choosing pivots when sublists of length 2
happened to be in order – most frequently the two 4.0s and the 1.0, 0.6 at the end. Good
presentation, with a list spread evenly, in columns, across the page, helps here. (Vertical listing
is rarely successful). Part (b) was generally well done, the two most popular errors being to put
0.6 in bin 5 or 0.4 in bin 5. A significant number who had sorted the numbers into increasing
order in part (a) proceeded to use a “first fit increasing” method here. In part (c) most candidates
calculated the lower bound correctly. Other candidates correctly stated that since the five largest
items were over half a bin in size they could not share a bin, so at least 5 bins would be needed.
A few simply stated ‘yes’ without justification, gaining no credit.

5. This was generally well done. A disappointingly large number of candidates only chose one
pivot per iteration, rather than choosing one pivot per sublist, and some candidates used lengthy
methods of presentation that isolated each sublist in turn, making it difficult to see if they were
choosing more than one pivot per iteration. The examiners would advise candidates to refrain
from showing this unnecessary detail and simply indicate the pivots selected at each iteration.
Some candidates did not select a pivot where the sublist was of order two, with the two items
being in the correct order, and some did not consistently pick ‘middle left’ or ‘middle right’
when the sublist was of even order. Candidates are reminded that when the items are being
transferred to the next line, the order of the items should be preserved, so if item Y is to the left
of item X in the current line, neither of them being a pivot, then Y should be to the left of X in
the next line. The best candidates allowed each item to become a pivot before declaring the sort
complete. Some candidates did not check that their final list was in alphabetical order. In part
(b) some candidates tried to apply the algorithm to the original unsorted list given at the start of
(a) and others did not discard the pivot at each stage, but generally the binary search was very
well done. A few candidates selected J as the first pivot, the specification makes it clear that
candidates must take the ‘middle right’ where necessary.

Edexcel Internal Review 16

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

6. Part (a) was done with mixed success. The majority of candidates gained full marks or three
marks. The most common errors were to have HIJ after the second pass and neglecting to
choose a pivot on the third pass with the entry MR. Most knew their alphabet, but not all. There
was a temptation to go into too much detail about the choice of pivot, to the extent that
examiners were not always sure that more than one pivot was being considered per iteration. It
is an important feature of the quick sort that the number of pivots can potentially double at each
iteration, so the selection of multiple pivots must be clearly shown. Some candidates did not
abbreviate the names, by using the initial letter and this slowed them down.
Part (b) was usually very well done. The most common errors were not rejecting the pivot and
not making a decision when Hannah was left. Some candidates added Hugo to the list and then
found him, others confused Hannah and Hugo.

7. This proved a good starter question for the candidates with many gaining full marks. Some
candidates were inconsistent in their pivot choice, the specification requires that they round up.
Some incorrectly retained the pivot each time – often leading to a situation where they selected
Nicky twice, once as the first pivot and once as the final pivot. Some candidates insisted on
placing Nigel in the list – or locating the position in which Nigel should be added to the list. The
binary search algorithm is both used to locate an item in the list and to demonstrate its absence.
A few candidates confused binary search and quick sort.

8. This was generally well done. Many candidates completed the quick sort, wasting time. Some
candidates did not understand the difference between an exchange and a pass in a bubble sort.
Most candidates carried out the search well, but many did not give the location of the value. A
large number are still assuming that the item is in the list, making statements such as ‘down to
one item so found’. A surprisingly large minority of candidates used the mean of the end
numbers in the remaining list to create a ‘pivot’ which is unacceptable.

Edexcel Internal Review 17

D1 Algorithms - Binary search PhysicsAndMathsTutor.com

9. This question was often well answered. Most candidates correctly competed part (a), although a
very few stated that the list should be in ascending rather than alphabetical order. Most could
correctly name and use a suitable sorting algorithm in part (b), although some did not make their
stopping statement clear and a few used a shuttle sort (not in this specification) stating that it
was a bubble sort. A surprisingly large minority confused the order of the alphabet with S and P
(and then M and N) most frequently transposed. Part (c) was usually well done but candidates
must make their pivots – and the order in which they select their pivots, clear. Candidates must
remember to discard their pivots and note that the specification instructs them to ‘round up’.
Once again the stopping/found statement was sometimes missing, and some candidates assumed
the presence of N, stating that once they had got down to 1 term only, that term must be N.

10. Many candidates were able to gain full marks on this question. The most common errors in part
(a) were in re-ordering the letters in the sub-lists and choosing the pivots inconsistently. A
surprising number of candidates seemed unsure of the alphabet. Part (b) was well done by the
majority of candidates. A surprising number tried to use an unsorted list for their search, gaining
no marks and others omitted to discard the pivot. The commonest error was in failing to select
Morris after correctly selecting Palmer then Halliwell. A few candidates did not make the order
in which they selected the pivots clear making it impossible to give credit.

Edexcel Internal Review 18