2.1.2b Binary Search — OCR J277

🔒

Unlock Everything

£7.99/month

or £59/year

What Is a Binary Search?

A binary search is an efficient searching algorithm that works by repeatedly halving the search space. It compares the target to the middle element of a sorted list, then eliminates the half that cannot contain the target.

Critical requirement: The list must be sorted before binary search can be applied. This is its key limitation compared to linear search.

How Binary Search Works — Step by Step

Step 1 — Find the midpoint

Calculate the middle index: mid = (low + high) ÷ 2 (integer division). Compare list[mid] with the target.

Step 2 — Compare

If list[mid] == target → found! Return mid.
If list[mid] < target → target must be in the right half. Set low = mid + 1.
If list[mid] > target → target must be in the left half. Set high = mid - 1.

Step 3 — Repeat

Repeat with the new search range (low to high) until the target is found, or low > high (target not in list).

Worked Example — Trace Table

Sorted list: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] — Search for 23

idx 0

idx 1

idx 2

idx 3

idx 4

idx 5

idx 6

idx 7

idx 8

idx 9

16
mid①

23
✓found

Trace table:

Pass	low	high	mid	list[mid]	Compare to 23	Result
1	0	9	4	16	16 < 23	low = mid+1 = 5
2	5	9	7	45	45 > 23	high = mid-1 = 6
3	5	6	5	23	23 == 23	Found at index 5

Only 3 comparisons needed for a 10-item list — compare with up to 10 for linear search.

Pseudocode

// Binary search — list must be sorted FUNCTION binarySearch(list, target) low = 0 high = length(list) - 1 WHILE low <= high mid = (low + high) DIV 2 IF list[mid] == target THEN RETURN mid // Found! ELSE IF list[mid] < target THEN low = mid + 1 // Target in right half ELSE high = mid - 1 // Target in left half END IF END WHILE RETURN -1 // Not found END FUNCTION

Why Binary Search Is Faster — O(log n)

Binary search is O(log₂n) — with each comparison, the search space is halved. For a sorted list of 1024 items, binary search needs at most 10 comparisons (log₂1024 = 10), while linear search could need 1024.

List size (n)	Binary: max comparisons (log₂n)	Linear: max comparisons
8	3	8
64	6	64
1,024	10	1,024
1,048,576	20	1,048,576

Advantages and Disadvantages

Advantages	Disadvantages
Much faster than linear search for large lists — O(log n)	Requires the list to be sorted first
Efficient — eliminates half the remaining items each pass	Sorting adds overhead if data is not already sorted
Suitable for large datasets	More complex to implement than linear search
Predictable maximum comparisons	Not suitable for data that changes frequently

Comparison: Linear vs Binary Search

Feature	Linear Search	Binary Search
Sorted list required?	No	Yes
Time complexity (worst)	O(n)	O(log n)
Best for	Small / unsorted lists	Large sorted lists
How it searches	One by one from start	Halves search space each time
Not found return	-1	-1
Implementation	Simpler	More complex

Exam tip: In binary search trace table questions, always show low, high, and mid values for each pass. Remember: mid = (low + high) DIV 2 (integer division — round down). After finding mid, if list[mid] < target then low = mid + 1; if list[mid] > target then high = mid - 1. The search ends when low > high (not found) or list[mid] == target (found). Always state the index returned, not just the value.

⚠️ Common Mistakes

Forgetting that binary search requires a sorted list — always state this as a prerequisite
Using the wrong mid formula — OCR exams use integer division (DIV): (low + high) DIV 2
Setting low = mid (not mid+1) or high = mid (not mid-1) — this can cause infinite loops
Confusing what "low > high" means — it means not found, not an error
Saying binary search is always better — for small or unsorted lists, linear search may be preferred

✅ Notes completed!

▶

Video coming soon

Click slide or press arrow keys to navigate

Worksheet — 2.1.2b Binary Search

8 questions · 20 marks

Q1State one requirement for a binary search to work.[1]

✅ Mark scheme

The list must be sorted (in ascending or descending order) [1].

Q2Describe how a binary search works.[3]

✅ Mark scheme

Find the middle element of the list [1]; compare it with the target — if equal, found; if target is greater, search the right half; if target is smaller, search the left half [1]; repeat with the new half until found or no elements remain [1].

Q3Perform a binary search on the sorted list [3, 7, 11, 14, 18, 22, 27, 31] for target = 22. Show a full trace table.[5]

✅ Mark scheme

Pass 1: low=0, high=7, mid=3, list[3]=14. 14<22 so low=4 [1]. Pass 2: low=4, high=7, mid=5, list[5]=22. 22==22 [1], return index 5 [1]. 2 comparisons [1]. Correct layout with low/high/mid columns [1].

Q4State the formula for calculating the mid-point index in a binary search.[1]

✅ Mark scheme

mid = (low + high) DIV 2 [1] (integer/floor division).

Q5A binary search is performed on a list of 1024 items. What is the maximum number of comparisons needed?[2]

✅ Mark scheme

10 comparisons [1] — because log₂(1024) = 10 [1].

Q6Give two advantages and one disadvantage of binary search compared to linear search.[3]

✅ Mark scheme

Advantages (any two): much faster for large lists [1]; O(log n) efficiency [1]; eliminates half the data per comparison [1]. Disadvantage: requires the list to be sorted [1].

Q7A binary search for target = 5 on list [1, 3, 5, 7, 9, 11, 13] returns what index? Show your working.[3]

✅ Mark scheme

Pass 1: low=0, high=6, mid=3, list[3]=7. 7>5, high=2 [1]. Pass 2: low=0, high=2, mid=1, list[1]=3. 3<5, low=2 [1]. Pass 3: low=2, high=2, mid=2, list[2]=5. Found at index 2 [1].

Q8A student says "binary search is always better than linear search." Evaluate this statement.[2]

✅ Mark scheme

Not always — binary search is only better for large sorted lists [1]. Linear search is preferable when the list is unsorted or too small to justify sorting [1].

out of 20 — self-mark above

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 10

Click to reveal definition

🎉

Complete!

Term	Definition

What Is a Binary Search?

How Binary Search Works — Step by Step

Worked Example — Trace Table

Pseudocode

Why Binary Search Is Faster — O(log n)

Advantages and Disadvantages

Comparison: Linear vs Binary Search

Worksheet — 2.1.2b Binary Search

Mini Test — 2.1.2b Binary Search