IB Computer Science HL · Year 2 · Lesson 7

Linear and Binary Search

Construct and trace both search algorithms, then choose a method based on ordering, indexing and efficiency requirements.

Paper 250 minutesB2.4.2

Answer first. Reveal only after you have committed to a response.

Course home IA hub 2027 case study

Today’s targets

What you need to be able to do

2 / 10

construct and trace a linear search;
construct and trace a binary search on appropriately ordered data;
compare the efficiency of linear and binary search;
select a search technique based on the data organization and search key.

B2.4.2

Paper 2 habitRead the command term and the data given. A technically correct answer still needs to answer the exact task.

Page 2 of 10

Learn + retrieve

Rapid Recall Deck

3 / 10

Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.

Recall deck answers

How does linear search work? Check items one by one until the target is found or the data is exhausted.
What data ordering does linear search require? None; it can search unsorted data.
How does binary search work? Repeatedly compare with the middle item and discard the half that cannot contain the target.
What condition must normally be true before binary search can be used? The data must be ordered by the key being searched, or an equivalent searchable index must exist.
What is the typical time complexity of linear search? O(n).
What is the typical time complexity of binary search? O(log n).
Why can binary search outperform linear search on large sorted data? Each comparison eliminates about half of the remaining search range.
Why might linear search still be appropriate? The data may be unsorted, small, searched infrequently, or ordered by a different key.
If a directory is sorted by name, which lookup suits binary search? Searching by name, because the ordering matches the search key.
Why may searching that same directory by phone number require linear search? If it is not also sorted or indexed by phone number, binary search cannot safely discard half based on phone-number comparisons.

Page 3 of 10

B2.4.2 · Linear search

Trace one item at a time

4 / 10

names = ["Ava", "Ben", "Cara", "Drew", "Eli"]
target = "Drew"

index = 0
found = -1

while index < len(names) and found == -1:
    if names[index] == target:
        found = index
    else:
        index += 1

print(found)

Trace the search

State the value checked on each iteration and the final output.

Iteration 1 starts at index 0.

Stop when the target is found or the List is exhausted.

The algorithm checks Ava at index 0, Ben at 1, Cara at 2, then Drew at 3. It sets found = 3 and the loop stops. Final output: 3.

Page 4 of 10

Construct

Write linear search without a built-in search

5 / 10

Teacher-created exam restrictionFor this task, do not use in, .index() or any search library.

Construct `linear_search(data, target)`

Return the index of the first matching value, or -1 when the target is not present.

Traverse from the first item to the last.

Compare each item with target.

Return immediately when a match is found; otherwise return -1 after the loop.

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1

Page 5 of 10

Binary search

Discard half of an ordered search range

6 / 10

Sorted data["Ava", "Ben", "Cara", "Drew", "Eli", "Faye", "Gus"], target "Eli".

Trace low, high and mid

Start low = 0, high = 6.

Each step — calculate mid, compare names[mid] with Eli, then update low or high.

Stop when Eli is found or low passes high.

low=0, high=6, mid=3 → Drew. Eli is later alphabetically, so low=4.
low=4, high=6, mid=5 → Faye. Eli is earlier, so high=4.
low=4, high=4, mid=4 → Eli. Found at index 4.

Page 6 of 10

Construct binary search

Make the range shrink correctly

7 / 10

Construct `binary_search(data, target)`

Assume data is already sorted in ascending order. Return the matching index or -1.

Bounds — maintain the current search interval.

Middle — calculate the middle index.

Three outcomes — handle found, search-lower-half and search-upper-half cases.

Not found — return -1 when the interval is exhausted.

def binary_search(data, target):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Page 7 of 10

Efficiency + selection

The search key matters

8 / 10

DirectoryA phone directory is sorted alphabetically by name. Each record also stores a phone number.

Find a phone number from a name

The data is ordered by the key being searched. Binary search can eliminate half the remaining names after each comparison.

Find a name from a phone number

The records are not ordered by phone number. Without a separate phone-number index, binary search is not valid for this lookup.

Explain the algorithm choice

Why is binary search suitable for the first lookup but linear search may be required for the second?

Binary search requirement — ordering/indexing must match the search key.

Efficiency — O(log n) versus O(n) when the precondition is satisfied.

The directory is sorted by name, so comparing a target name with the middle record tells the algorithm which half can be discarded; binary search therefore gives O(log n) search growth. A phone-number lookup does not have that ordering information, so unless a separate index or ordering by phone number exists, the safe method is to inspect records one by one using linear search, which is O(n).

Page 8 of 10

Exam lens

Teacher-created Paper 2 practice

9 / 10

1. A sorted List contains [4, 9, 13, 18, 25, 31, 42]. Trace binary search for target 25 by recording low, high and mid until the target is found.

2. Explain why binary search cannot be safely applied to [18, 4, 31, 9, 25] without first changing how the data is organized.

3. Construct a linear search function that returns True when a target exists and False otherwise. Do not use in.

low=0, high=6, mid=3 → 18, so low=4. Then low=4, high=6, mid=5 → 31, so high=4. Then low=4, high=4, mid=4 → 25.
The data is not sorted by the values being compared, so a middle comparison does not tell which half can be safely discarded.

def contains(data, target):
    for value in data:
        if value == target:
            return True
    return False

Page 9 of 10

Homework

Finish the learning cycle

10 / 10

IA — main task

Look at any search or lookup behaviour planned for the IA. Record what key is searched and whether the data is naturally ordered or indexed by that key.

IA check complete

Syllabus — short retrieval

Redo the binary-search trace on page 9 without Reveal, then explain in one sentence why sorted data is a precondition rather than just a performance improvement.

Retrieval complete

Designed by David Xu

Educators and students are welcome to use these materials for non-commercial teaching and learning with attribution. Please share the original link when possible. Reposting, redistributing modified copies, removing attribution, or commercial use requires prior permission.

End of Lesson 7.

Linear and Binary Search

What you need to be able to do

Rapid Recall Deck

Trace one item at a time

Trace the search

Write linear search without a built-in search

Construct linear_search(data, target)

Discard half of an ordered search range

Trace low, high and mid

Make the range shrink correctly

Construct binary_search(data, target)

The search key matters

Find a phone number from a name

Find a name from a phone number

Explain the algorithm choice

Teacher-created Paper 2 practice

Finish the learning cycle

IA — main task

Syllabus — short retrieval

Construct `linear_search(data, target)`

Construct `binary_search(data, target)`