SLIDE 1
CSZone.co.uk
Click to reveal · Arrow keys also work
OCR J277 · Component 2 · Topic 2.1.3b

Searching Algorithms
Binary Search

Prerequisite · Apply · Trace · Efficiency

CSZone OCR GCSE Computer Science J277
Learning Objectives

By the end of this video you will be able to...

Describe how a binary search works in plain English — including the prerequisite that data must be sorted, and exactly how the midpoint, low, and high pointers update at each step
Write and identify binary search pseudocode — recognise its structure in unfamiliar code using its three key signatures: midpoint calculation, three-way comparison, and pointer update
Apply binary search to a sorted data set — show each iteration with low, high, mid values and the comparison made, until the target is found or confirmed absent
Complete and interpret trace tables for binary search — tracking low, high, mid, data[mid] and the comparison result for both found and not-found cases
State the efficiency of binary search and compare it to linear search — explain why it is faster on large sorted lists and when each algorithm is more appropriate
⚡ The spec explicitly lists binary search under "apply algorithm to a data set" — step-by-step application questions appear on virtually every Component 2 paper.
Binary Search — The Concept

What is a binary search?

⚠ PREREQUISITE — CRITICAL
Binary search only works on sorted data. The list must be in ascending or descending order before you start. If the data is unsorted, use linear search instead.
DEFINITION
Binary search works by repeatedly halving the search space. It finds the middle element and compares it to the target. If it matches, the search is done. If not, it eliminates the half that cannot contain the target and searches the remaining half.
THE PROCESS IN PLAIN ENGLISH
1.
Set low = first index (0), high = last index (n−1)
2.
Calculate mid = (low + high) DIV 2
3.
If data[mid] == target → found. Stop.
4.
If target < data[mid] → target is in left half → set high = mid − 1
5.
If target > data[mid] → target is in right half → set low = mid + 1
6.
Repeat from step 2. If low > high → not found.
VISUAL — WHY HALVING IS SO POWERFUL
Consider a sorted list of 16 elements. Binary search halves the search space with every comparison:
Start:
16 elements
After 1:
8 elements
After 2:
4 elements
After 3:
2 elements
After 4:
1 element — done!
16 elements → found in at most 4 comparisons. Linear search might need 16. For 1,000,000 elements: binary search needs at most 20 comparisons.
⚡ The key exam point: binary search requires sorted data. If an exam question gives you an unsorted list and asks which search to use, the answer is linear search. If it asks you to apply a binary search to an unsorted list — always sort it first.
Binary Search — Pseudocode

Binary search in pseudocode

FULL PSEUDOCODE
// Sorted array: data[] · target to find low = 0 high = LEN(data) - 1 found = FALSE WHILE low <= high AND found == FALSE mid = (low + high) DIV 2 IF data[mid] == target THEN OUTPUT "Found at index: ", mid found = TRUE ELSE IF data[mid] < target THEN low = mid + 1 ELSE high = mid - 1 END IF END WHILE IF found == FALSE THEN OUTPUT "Not found" END IF
⚡ OCR won't ask you to write this from memory. But you must identify it from given code. Three key signatures: midpoint calculation with DIV, three-way IF/ELSE IF/ELSE comparison, and updating low or high. All three together = binary search.
ANATOMY — EACH KEY LINE EXPLAINED
low = 0, high = LEN-1 — initialise the search boundaries to the full list.
WHILE low <= high AND found==FALSE — loop continues while there is still a valid range to search and the target hasn't been found.
mid = (low+high) DIV 2 — integer division gives the middle index of the current range.
data[mid] < target → low = mid+1 — target is in the right half, discard the left.
ELSE → high = mid-1 — target is in the left half, discard the right.
After the loop: if found==FALSE, the WHILE condition became low>high — the search space is empty. Target is not present.
Why DIV and not /? DIV gives the integer quotient — no decimal places. If low=3 and high=6, mid = 9 DIV 2 = 4 (not 4.5). Array indices must be whole numbers. This is the same DIV from pseudocode — always use it for midpoint calculations.
Applying Binary Search

Applying it step by step — target found

SORTED LIST (indices 0–9)  ·  TARGET = 35
1
4
7
10
14
18
23
29
35
42
0
1
2
3
4
5
6
7
8
9
■ low■ mid■ high■ found■ eliminated
ITERATION 1
low=0   high=9   mid=(0+9) DIV 2 = 4
1
4
7
10
14
18
23
29
35
42
data[4] = 14  ·  35 > 14 → target in right half
→ low = mid+1 = 5   (eliminate indices 0–4)
ITERATION 2
low=5   high=9   mid=(5+9) DIV 2 = 7
1
4
7
10
14
18
23
29
35
42
data[7] = 29  ·  35 > 29 → target in right half
→ low = mid+1 = 8   (eliminate indices 5–7)
ITERATION 3
low=8   high=9   mid=(8+9) DIV 2 = 8
1
4
7
10
14
18
23
29
35
42
data[8] = 35  ·  35 == 35 → MATCH FOUND!
→ found=TRUE · OUTPUT index 8
RESULT — 3 comparisons
Target 35 found at index 8. Compare with linear search: linear would need 9 comparisons to reach index 8. Binary needed only 3.
⚡ Always show your working: write low, high, mid and the comparison at each iteration. Each step is worth marks — not just the final answer.
Applying Binary Search

Applying it — target not found

SAME SORTED LIST  ·  TARGET = 20 (not in list)
1
4
7
10
14
18
23
29
35
42
0
1
2
3
4
5
6
7
8
9
ITERATION 1  ·  low=0, high=9, mid=4
data[4]=14  ·  20 > 14 → right half  ·  low = 5
ITERATION 2  ·  low=5, high=9, mid=7
data[7]=29  ·  20 < 29 → left half  ·  high = 6
ITERATION 3  ·  low=5, high=6, mid=5
data[5]=18  ·  20 > 18 → right half  ·  low = 6
ITERATION 4  ·  low=6, high=6, mid=6
data[6]=23  ·  20 < 23 → left half  ·  high = 5
CHECK LOOP CONDITION
low = 6   high = 5
low > high → the search space is empty. Every possible position for 20 has been eliminated. The WHILE condition low <= high is now FALSE — loop exits.
RESULT — 4 comparisons, NOT FOUND
Target 20 is not in the list. found=FALSE after loop → output "Not found". Binary search confirmed absence in just 4 comparisons. Linear would need all 10.
⚡ The not-found exit condition is low > high — not "ran out of elements". This means the sub-array to search has become empty. When low overtakes high, every possibility has been eliminated. This is a very common exam question.
Trace Tables

Trace table — binary search, target found

ALGORITHM BEING TRACED
data = [1,4,7,10,14,18,23,29,35,42] target = 35 low = 0   high = 9   found = FALSE WHILE low <= high AND found == FALSE mid = (low + high) DIV 2 IF data[mid] == target THEN OUTPUT mid found = TRUE ELSE IF data[mid] < target THEN low = mid + 1 ELSE high = mid - 1 END IF END WHILE
Yellow = changed  ·  Green = output
Table builds right → each click adds one iteration. Target 35 is found in 3 iterations at index 8.
TRACE TABLE
lowhighmiddata[mid]comparisonupdateOUTPUT
0941435>14low=5
572935>29low=8
883535==35 ✓found=TRUE8
Only write a value in a cell when it changes. high stays 9 in iteration 2 and 3 — leave those cells blank. low changes in iterations 1 and 2 — write the new value.
⚡ Exam: "What is the value of mid after iteration 2?" → 7. "How many comparisons?" → 3. "What is output?" → 8.
Trace Tables

Trace table — target not found

SAME LIST — TARGET = 20 (absent)
data = [1,4,7,10,14,18,23,29,35,42] target = 20 ← not in list low = 0   high = 9   found = FALSE // same WHILE loop as before // loop exits when low > high
Four iterations before low overtakes high. Each iteration eliminates half the remaining range. Target 20 sits between 18 and 23 — binary search will narrow in, then confirm absence.
⚡ Two key exam points on not-found traces: (1) found column stays blank throughout — it never changes from FALSE. (2) Add a final row showing "low > high — exit loop" and the "Not found" output below the table, not inside it.
TRACE TABLE — NOT FOUND
lowhighmiddata[mid]comparisonupdate
0941420>14low=5
572920<29high=6
651820>18low=6
662320<23high=5
low=6, high=5 → low>high → EXIT LOOP → output "Not found"
Total comparisons: 4. high changes in iterations 2 and 4 (write new value). low changes in iterations 1 and 3 (write new value). mid and data[mid] change every row. found column is entirely blank — it was never set to TRUE.
Efficiency

Efficiency — binary search vs linear search

BINARY SEARCH EFFICIENCY
BEST
1
Target is the first midpoint. Found in a single comparison — the target happens to be exactly in the middle of the list on the first check.
AVERAGE
log₂(n)
Approximately log₂(n) comparisons. Each comparison halves the search space. For 1,024 items: at most 10 comparisons. For 1,000,000: at most 20.
WORST
log₂(n)
Target is absent or at a leaf. The search halves until a single element remains, which either matches or doesn't. Still only log₂(n) comparisons.
⚡ The spec doesn't require log₂(n) notation — but knowing that binary search is much faster than linear on large sorted data is expected. The key fact: doubling the list size only adds one more comparison for binary search.
COMPARISON TABLE
LINEAR SEARCHBINARY SEARCH
Sorted data needed?NoYES — required
Best case11
Worst casenlog₂(n)
1,000 itemsup to 1,000up to 10
1,000,000 itemsup to 1,000,000up to 20
WHEN TO USE WHICH
Use linear search when data is unsorted, or the list is small.
Use binary search when data is sorted and the list is large — the efficiency gain is enormous.
If data is unsorted but binary search is needed — sort it first, then apply binary search.
⚡ Exam question: "Give one reason why binary search is more efficient than linear search." Answer: binary search halves the search space with each comparison, so it requires far fewer comparisons than linear search for large datasets.
Identify from Code

Identifying binary search from given code

THREE SIGNATURES OF BINARY SEARCH
SIGNATURE 1 — MIDPOINT CALCULATION
A line computing mid using (low + high) DIV 2 or equivalent. This is unique to binary search — linear search has no midpoint.
SIGNATURE 2 — THREE-WAY COMPARISON
IF equal to target (found) · ELSE IF less than target (update low) · ELSE (update high). Three branches, not two.
SIGNATURE 3 — POINTER UPDATE
low = mid + 1 or high = mid − 1 lines that narrow the search range. The loop condition checks low <= high.
All three must be present. Renamed variables don't change the identification — the structure is what matters.
EXAM QUESTION STYLE — "NAME THIS ALGORITHM"
lo = 0 hi = LEN(arr) - 1 flag = FALSE WHILE lo <= hi AND flag == FALSE centre = (lo + hi) DIV 2 ← ① IF arr[centre] == key THEN flag = TRUE ← ② ELSE IF arr[centre] < key THEN lo = centre + 1 ← ③ ELSE hi = centre - 1 ← ③ END IF END WHILE
Renamed: lo/hi/centre/flag/arr/key instead of low/high/mid/found/data/target. Doesn't matter. All three signatures present: midpoint ①, match test ②, pointer update ③. This is binary search.
⚡ "What algorithm does this code show?" — binary search. Mark scheme accepts "binary search" or "half-interval search". Always justify your answer by identifying at least one of the three signatures.
Exam Practice

Binary search — applying to data sets

Question 1 — 4 marks
A binary search is performed on the sorted list below, looking for 17.
List: [2, 5, 8, 11, 17, 23, 29, 35]

Show ALL iterations, stating the values of low, high and mid at each step and the comparison made.
Answer — Q1
Iter 1: low=0, high=7, mid=3, data[3]=11. 17>11 → low=4
Iter 2: low=4, high=7, mid=5, data[5]=23. 17<23 → high=4
Iter 3: low=4, high=4, mid=4, data[4]=17. 17==17 → FOUND at index 4
Comparisons: 3
Question 2 — 3 marks
Using the same list, perform a binary search for 6. Show all iterations and state the final output.
List: [2, 5, 8, 11, 17, 23, 29, 35]
Answer — Q2
Iter 1: low=0, high=7, mid=3, data[3]=11. 6<11 → high=2
Iter 2: low=0, high=2, mid=1, data[1]=5. 6>5 → low=2
Iter 3: low=2, high=2, mid=2, data[2]=8. 6<8 → high=1
Now: low=2, high=1 → low>high → loop exits → NOT FOUND
Question 3 — 3 marks
The pseudocode below performs a search.
(a) Name the algorithm shown.
(b) Give one reason how you identified it.
(c) The list searched is [3, 9, 15, 21, 27, 33]. State the output when key = 21.
lo=0 : hi=LEN(arr)-1 : flag=FALSE WHILE lo<=hi AND flag==FALSE centre=(lo+hi) DIV 2 IF arr[centre]==key THEN flag=TRUE ELSE IF arr[centre]<key THEN lo=centre+1 ELSE hi=centre-1 END IF END WHILE
Exam Practice — Answers

Question 3 answered + common mistakes

Q3 ANSWER
(a) Binary search (1 mark)
(b) Identified by the midpoint calculation (lo+hi) DIV 2, the three-way IF/ELSE IF/ELSE comparison, and the pointer update (lo=centre+1 or hi=centre-1) (1 mark)
(c) arr=[3,9,15,21,27,33], key=21:
Iter 1: lo=0, hi=5, centre=2, arr[2]=15. 21>15 → lo=3
Iter 2: lo=3, hi=5, centre=4, arr[4]=27. 21<27 → hi=3
Iter 3: lo=3, hi=3, centre=3, arr[3]=21. 21==21 → flag=TRUE → output index 3 (1 mark)
NOTE ON PART (b) — IDENTIFICATION
One reason is enough for 1 mark. The strongest answer is the midpoint calculation — it's unique to binary search. A loop that checks all elements is linear search; a loop with a midpoint and halving is binary search.
COMMON MISTAKES — BINARY SEARCH
1
Applying to unsorted data. Binary search only works on sorted data — applying it to an unsorted list gives incorrect results. Always verify the list is sorted before applying.
2
Using regular division instead of DIV. Mid must be an integer. (3+6)/2 = 4.5 — that's not a valid index. Always use (3+6) DIV 2 = 4.
3
Wrong pointer update direction. If target > data[mid], move low up (low = mid+1). If target < data[mid], move high down (high = mid-1). Swapping these searches the wrong half.
4
Not showing all iterations in exam. When asked to "apply the algorithm", show every iteration — low, high, mid, comparison — until found or low>high. Partial working loses marks.
⚡ Mistakes 1 and 3 cause incorrect answers. Always check: is the list sorted? Am I moving low UP or high DOWN correctly?
Advantages & Disadvantages

Binary search — strengths and weaknesses

✓ ADVANTAGES
Very fast on large sorted datasets — worst case is log₂(n). For one million items, at most 20 comparisons.
Significantly fewer comparisons than linear search when data is sorted — the larger the list, the greater the advantage.
Efficient confirmation of absence — quickly proves a target is not present without checking every element.
⚡ "Give one advantage of binary search over linear search." Answer: it is much faster / requires far fewer comparisons on large sorted datasets because it halves the search space with each comparison.
✗ DISADVANTAGES
Data MUST be sorted first — if the data is unsorted, you must sort it before searching, which costs extra time. Linear search needs no sorting.
More complex to implement — requires tracking three pointers (low, high, mid) and handling the three-way comparison correctly.
No advantage on small lists — for a 5-element list, binary search offers no real speed benefit over linear search.
⚡ "Give one disadvantage of binary search." Answer: it requires the data to be sorted before it can be applied — if the data is unsorted, linear search must be used instead, or the data must be sorted first.
Summary

2.1.3b — Binary Search

⚠ PREREQUISITE
Data MUST be sorted. Works on ascending or descending ordered lists only.
HOW IT WORKS
Set low=0, high=n-1. Repeatedly find mid=(low+high) DIV 2. If data[mid]==target → found. If target>data[mid] → low=mid+1. Else → high=mid-1. Exit when found OR low>high.
IDENTIFYING FROM CODE
Three signatures: (1) midpoint calculation with DIV, (2) three-way IF/ELSE IF/ELSE, (3) low or high pointer updated to mid±1. All three = binary search.
EFFICIENCY
Best: 1 comparison. Worst/Average: log₂(n). For 1,000,000 items: at most 20 comparisons vs linear's 1,000,000. Enormously faster on large sorted data.
BINARY vs LINEAR
Binary advantage: far fewer comparisons on large sorted data. Binary disadvantage: requires sorted data, more complex to implement. Use binary when data is sorted and list is large. Use linear when data is unsorted or list is small.
2.1.3b Complete

That's Binary Search done!

Next up: 2.1.3c — Bubble Sort

📝
MARKED WORKSHEET
CSZone.co.uk
🎯
QUIZ
CSZone.co.uk
📊
SLIDES
CSZone.co.uk