IB CS Core — Topics 1–5 (SL & HL) · lesson 3 of 4 · 25 min
Linear and binary search
topic: Topic 4
component:
Linear search and binary search
Searching is one of the most fundamental operations in computing. The IB CS syllabus requires you to trace, compare, and evaluate both linear and binary search.
Linear search
Linear search examines each element in sequence until the target is found or the list is exhausted. It works on unsorted and sorted lists.
- PROCEDURE linearSearch(arr, target)
- FOR i FROM 0 TO arr.length – 1
- IF arr[i] = target THEN
- RETURN i
- END IF
- END FOR
- RETURN -1 // not found
- END PROCEDURE
Binary search
Binary search works only on sorted lists. It repeatedly halves the search space by comparing the target to the middle element.
- PROCEDURE binarySearch(arr, target)
- low ← 0
- high ← arr.length – 1
- WHILE low ≤ high
- mid ← (low + high) DIV 2
- IF arr[mid] = target THEN
- RETURN mid
- ELSE IF arr[mid] < target THEN
- low ← mid + 1
- ELSE
- high ← mid – 1
- END IF
- END WHILE
- RETURN -1
- END PROCEDURE
- Trace: search for 42 in [5, 12, 23, 42, 67, 89, 95]
low=0, high=6, mid=3. arr[3]=42. Found! Return 3.
Only 1 comparison needed because 42 happened to be the middle element.
Trace: search for 23 in [5, 12, 23, 42, 67, 89, 95]
Step 1: low=0, high=6, mid=3. arr[3]=42 > 23. high ← 2.
Step 2: low=0, high=2, mid=1. arr[1]=12 < 23. low ← 2.
Step 3: low=2, high=2, mid=2. arr[2]=23. Found! Return 2.
IB exam questions frequently ask you to trace a binary search step by step, showing the values of low, high, and mid at each iteration. Always show your working.
Knowledge check
- Question of
- Hide hint
- Show hint
✓ Correct! ✕ Not quite
- Try again
- See results
- Next question
- Check answer
Previous lesson: Binary, hexadecimal and number bases
Back to IB CS Core — Topics 1–5 (SL & HL)
Next lesson: Singly and doubly linked lists