IB COMPUTER SCIENCE | B2.4.2 Linear and Binary Search

Lesson objective

Construct and trace linear and binary search algorithms, retrieve matching records and explain sorted-data requirements, boundary updates and failure results.

Learn

B2.4.2 | LINEAR AND BINARY SEARCH

01 | RETRIEVE THE RIGHT ITEM

A library program knows the book ID a student requested, but it still needs to find the matching stored record. A search algorithm systematically examines data to locate a target, or establish that it is absent.

The target is the value we seek. The collection contains candidate items. Our first functions return the zero-based index of a matching item, or -1 when no match exists. The caller can use a valid index to retrieve the item.

We will construct and trace linear and binary search in Python, with equivalent Java methods. Both algorithms retrieve data, but they have different prerequisites and search strategies.

02 | VALUES AND INDEXES ARE DIFFERENT

Index Stored value
0 18
1 7
2 25
3 4
4 12

The target 25 is stored at index 2. Returning 2 means “the match is at this position”; returning 25 would instead return the value itself. Be explicit about the function’s result.

Python lists and Java arrays use zero-based indexes: the first index is 0 and the last is length − 1. A human-facing “third item” therefore has index 2.

We choose -1 as a not-found result because it is not a valid non-negative array index. Python does allow negative indexing, so the caller must test the result before using it as an index.

03 | LINEAR SEARCH: CHECK IN ORDER

Imagine looking through an unsorted pile of cards. Start with the first card, compare its value with the target, then move to the next card if it is not a match. Stop at a match or after the final card.

This is linear search, also called sequential search. It does not require sorted data. It can search numbers, names or records as long as we have a suitable equality test.

For [18, 7, 25, 4, 12] and target 25: compare 18, then 7, then 25. The third comparison succeeds, so return index 2 without examining 4 or 12.

04 | CONSTRUCT THE LINEAR SEARCH FUNCTION

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

values = [18, 7, 25, 4, 12]
print(linear_search(values, 25))
print(linear_search(values, 9))

The outputs are 2 and -1. range(len(values)) supplies the valid indexes. Each iteration compares one item with target, and return index exits the whole function immediately on a match.

The final return -1 is outside the loop. It is reached only after every candidate has failed. If it were inside the loop after the if, the function would wrongly report failure immediately after the first nonmatch.

The input list is not changed. For an empty list the loop has no iterations, so the function safely returns -1.

05 | TRACE A SUCCESSFUL LINEAR SEARCH

Comparison index values[index] Equals 25? Action
1 0 18 False Continue
2 1 7 False Continue
3 2 25 True Return 2

Record the index and the stored value in separate columns. They describe different information. There are three inspected items; no comparisons are made after returning.

A trace follows the exact code. Do not continue filling rows for indexes 3 and 4 merely because those indexes exist.

06 | TRACE FAILURE ALL THE WAY TO THE END

Comparison index Stored value Equals 9?
1 0 18 False
2 1 7 False
3 2 25 False
4 3 4 False
5 4 12 False

After the fifth failed comparison, the range is exhausted and the function returns -1. A nonmatch at one position does not prove absence from the whole list.

For n items, an unsuccessful linear search checks n equality comparisons. A target in the first position needs only one. An empty list needs none.

07 | DUPLICATES: WHAT DOES FOUND MEAN?

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

print(linear_search([7, 4, 7, 9], 7))

The result is 0 because this version stops at the first match from the left. It does not count occurrences or return every matching position.

A search contract should state whether it returns any match, the first match, the last match or all matches. These are different requirements.

To obtain every matching index with a linear scan, append matching indexes to a result list and return that list after the loop. Avoid an early return when more matches are required.

08 | RETRIEVE A RECORD USING A KEY

def find_book(books, wanted_id):
    for index in range(len(books)):
        if books[index]["id"] == wanted_id:
            return index
    return -1

books = [{"id": 18, "title": "Robots"},
         {"id": 7, "title": "Networks"},
         {"id": 25, "title": "Databases"}]
position = find_book(books, 7)
if position != -1:
    print(books[position]["title"])
else:
    print("Book not found")

The output is Networks. A search key is the field used to identify or compare candidate records; here it is id. The returned position gives access to the whole matching record.

Check position != -1 before indexing. In Python, books[-1] would retrieve the last book, creating a dangerous-looking success when the target was actually absent.

This example assumes every record has an id and that IDs are unique. Names and titles may be duplicated, so choose a key matching the retrieval requirement.

09 | BINARY SEARCH NEEDS ORDER

If cards are sorted, we can inspect a middle card. When that value is too small, every earlier card is also too small. We can discard that entire side without checking each item.

Binary search repeatedly narrows a sorted candidate interval by comparing the target with its middle value. Our version assumes ascending numerical order and constant-time indexed access.

For an unsorted collection, the direction deduction is invalid. A target can lie in the half that the algorithm wrongly discards. Checking a middle value alone does not make a search correct.

10 | LOW AND HIGH ARE INCLUSIVE INDEXES

We keep two boundaries: low is the smallest remaining candidate index; high is the largest. Both are included in the active interval. Initially low = 0 and high = len(values) − 1.

For eight values, the initial interval is indexes 0 through 7. It contains eight candidates, not seven. When low == high, one candidate remains and must still be checked.

When low > high, the interval is empty. That is how the loop detects that no candidate remains. The condition must be low <= high for this inclusive-boundary implementation.

11 | CALCULATE THE MIDDLE INDEX

low = 0
high = 7
middle = (low + high) // 2
print(middle)

The result is 3. Integer division // keeps the whole-number quotient, so the algorithm chooses the lower of the two middle indexes when the interval length is even.

middle is an index, not the middle stored value. In [3, 7, 11, 15, 19, 23, 27, 31], index 3 stores 15. Compare 15 with the target; do not compare the index 3 with the target.

An upper-middle convention can also work with compatible updates. Trace the convention actually used by the supplied code.

12 | UPDATE PAST THE CHECKED MIDDLE

Comparison What sorted order establishes Update
values[middle] == target Match found Return middle
values[middle] < target Middle and all earlier candidates are too small low = middle + 1
values[middle] > target Middle and all later candidates are too large high = middle − 1

The +1 and −1 exclude the already checked nonmatching middle. Setting low = middle or high = middle can leave the same interval unchanged, causing a loop that never finishes.

Only one boundary changes after a nonmatch. Keep the other boundary, because its side can still contain the target.

The invariant is: if the target is present and not yet found, at least one matching position remains within the inclusive interval. Correct updates preserve this fact.

13 | CONSTRUCT ITERATIVE BINARY SEARCH

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        elif values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

values = [3, 7, 11, 15, 19, 23, 27, 31]
print(binary_search(values, 27))
print(binary_search(values, 20))

The outputs are 6 and -1. The while loop tests whether any candidate remains. A match returns immediately; a nonmatch moves one boundary beyond middle. Failure is returned only after the interval becomes empty.

This code assumes the collection is already sorted ascending. It does not validate or sort the data itself. The function returns an index in the supplied collection, which is not necessarily an index in any earlier unsorted version.

14 | TRACE TARGET 27: FOLLOW EVERY BOUNDARY

Probe low before high before middle Value Decision / next state
1 0 7 3 15 15 < 27; low becomes 4
2 4 7 5 23 23 < 27; low becomes 6
3 6 7 6 27 Match; return 6

The active indexes shrink from 0–7 to 4–7 to 6–7. The third probe finds the target. A probe is one inspected midpoint; the if/elif code may perform more than one comparison during a probe.

The table labels low and high before the probe so you can use them to calculate middle. The decision column records the update for the next probe.

15 | TRACE TARGET 20: AN EMPTY INTERVAL

Probe low before high before middle Value Decision / next state
1 0 7 3 15 Too small; low = 4
2 4 7 5 23 Too large; high = 4
3 4 4 4 19 Too small; low = 5

The next test is low <= high, or 5 <= 4, which is false. There is no fourth midpoint access. The function returns -1.

Notice the third probe: low == high was still a valid one-item interval. Changing the loop to low < high would incorrectly skip such a final candidate.

16 | INTERACTIVE: STEP THROUGH BOTH SEARCHES

Enter up to 12 comma-separated integers from −99 to 99, or leave the list empty. Linear search preserves the supplied order. Binary search requires ascending order; this activity rejects an unsorted list instead of silently sorting it.

Key: CURRENT = inspected item; ACTIVE = remaining candidates; DISCARDED = excluded; FOUND = match. Labels accompany the colours.

Predict the next inspected index before clicking. Try 27, 20, the first value, the final value, one item, an empty list and duplicate values. Changing an input restarts the trace, so old results cannot be mistaken for results for the new data.

17 | TEST EMPTY AND ONE-ITEM COLLECTIONS

Data Target Expected result Reason
[] 7 -1 No candidates
[7] 7 0 Single candidate matches
[7] 3 -1 Single candidate too large
[7] 9 -1 Single candidate too small
[3, 7] 7 1 Second item must remain reachable

For an empty binary-search input, high starts at -1 while low is 0. The first condition is false, so the algorithm never indexes the empty collection.

These tests expose off-by-one errors more directly than a single large example. Also test absent targets below the minimum, between stored values and above the maximum.

18 | BINARY SEARCH AND DUPLICATE VALUES

For [2, 4, 4, 4, 8] and target 4, our algorithm initially checks middle index 2 and returns 2. It finds a matching occurrence, but does not promise the first occurrence at index 1.

This differs from the shown left-to-right linear search, which returns the first matching index. If duplicates exist, the algorithms can both be correct while returning different matching indexes under an “any match” contract.

If the task requires the first matching index, modify the algorithm explicitly rather than assuming binary search already guarantees it.

19 | EXTENSION: FIND THE FIRST DUPLICATE

def first_binary_match(values, target):
    low = 0
    high = len(values) - 1
    result = -1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] >= target:
            if values[middle] == target:
                result = middle
            high = middle - 1
        else:
            low = middle + 1
    return result

print(first_binary_match([2, 4, 4, 4, 8], 4))

This returns 1. A match is saved in result, but the search continues to its left to look for an earlier match. If no earlier match exists, the saved result survives until return.

Every iteration still removes about half the remaining interval, so the worst-case search time remains O(log n) under the same assumptions. This is an extension of the basic algorithm, not a requirement to change every search.

20 | JAVA: COMPLETE LINEAR AND BINARY METHODS

public class SearchExample {
    static int linearSearch(int[] values, int target) {
        for (int index = 0; index < values.length; index++) {
            if (values[index] == target) {
                return index;
            }
        }
        return -1;
    }

    static int binarySearch(int[] values, int target) {
        int low = 0;
        int high = values.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (values[middle] == target) {
                return middle;
            } else if (values[middle] < target) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] values = {3, 7, 11, 15, 19, 23, 27, 31};
        System.out.println(linearSearch(values, 27));
        System.out.println(binarySearch(values, 27));
    }
}

Both methods print index 6. Java integer division produces the required midpoint for these non-negative differences. low + (high − low) / 2 avoids adding two potentially large indexes before division.

Python integers do not have the same fixed-width overflow issue, so the earlier (low + high) // 2 is appropriate there. The boundary convention and updates are otherwise equivalent.

21 | COMPARING EFFICIENCY FAIRLY

Property Shown linear search Shown iterative binary search
Order required No Ascending
Best-case search time O(1) O(1)
Worst-case search time O(n) O(log n)
Auxiliary search space O(1) O(1)
Duplicate policy First match from left Any match reached

Let n be the number of items and assume constant-time equality, ordering and indexed access. An unsuccessful linear search inspects n items. Binary search reduces the interval by about half after each nonmatch.

For the shown midpoint convention and n >= 1, at most floor(log₂ n) + 1 midpoint probes are needed. Do not equate probes with every individual relational comparison in the source.

For 1,024 items, an unsuccessful linear search inspects all 1,024; the binary search uses at most 11 probes. A favourable binary target can be found in the first probe.

22 | INCLUDE SORTING AND DATA MAINTENANCE

Sorting an unsorted collection just to perform one small search may cost more than a single scan. If sorting uses O(n log n) time, a sort followed by one O(log n) search is dominated by the sort.

For many searches of a mostly unchanged collection, sorting once and reusing the order can be worthwhile. Frequent insertions or updates may add costs to preserving sorted order.

Sorting also changes positions. Keep each key attached to its record, and return positions in the collection actually searched. Sorting a separate list of keys without preserving record associations can retrieve the wrong data.

Binary search relies on efficient midpoint access. A linked list does not provide the same constant-time indexed access assumed in this lesson.

23 | WHY THE ALGORITHMS TERMINATE

Linear search moves to the next valid index after a nonmatch. The finite range is eventually exhausted. Binary search discards the inspected midpoint and one side after each nonmatch. Its nonempty interval therefore strictly shrinks.

The binary-search invariant says that an existing target remains among the candidates until found. Sorted order justifies discarding a side; the +1 and −1 updates ensure progress. Both correctness and termination matter.

If a program uses low = middle on a two-item interval, it can repeatedly choose the same lower middle. This is why copying a boundary update without its matching interval convention is risky.

24 | CONSTRUCT A SEARCH FROM A SCENARIO

A school stores student records in arrival order and wants one record for an exact student ID. A linear search is straightforward because the data is not ordered by ID. Compare each record’s ID, return its position on a match, and report failure only after the full scan.

A second system maintains a large array sorted by unique student ID and performs many lookups. Binary search is appropriate under the indexed-access assumption. Compare the middle record’s ID, not the whole record or its position, and retrieve the matching record after a valid result.

Before coding, specify the data representation, ordering, equality rule, returned result, duplicate policy and absent-target behaviour. These choices determine the correct algorithm interface.

25 | BUILD A TRACE THAT EXPLAINS THE PROCESS

For linear search, record the inspected index, value, equality result and action. For binary search, record low and high before the probe, calculated middle, middle value, comparison outcome and next boundary update.

Show the final result separately from intermediate candidates. A midpoint examined during a failed search is not a retrieved record. When low becomes greater than high, record the false loop test and return -1.

Use the command word Trace by following the supplied algorithm exactly. If the question instead says Construct, supply a complete algorithm with initialization, conditions, progress, success and failure paths.

26 | COMMON ERRORS TO AVOID

Error Consequence Correction
Return failure inside first nonmatch Later values never checked Return -1 after the loop
Search unsorted data with binary search Wrong half can be discarded Meet sorted-data precondition
Compare middle with target Compares an index rather than data Use values[middle]
Use low < high with inclusive bounds Final candidate can be skipped Use low <= high
Set low = middle after too-small value May repeat the same interval Use middle + 1
Use -1 as a Python index unchecked Returns last item on failure Test result before retrieval
Expect first duplicate from basic binary search May return another match State or implement duplicate policy

A good solution makes the search contract clear and tests the boundaries that are easiest to get wrong. Use the activities to justify each update rather than memorize the code without its meaning.

MATCH THE SEARCH IDEA

Terminology

Terminology

Search

A process locating a target or establishing its absence.

Data retrieval

Obtaining the required stored item or record.

Target

The value sought by a search.

Search key

The field or value used to compare candidate records.

Index

A position used to access an item in an indexed collection.

Zero-based indexing

A convention with first index 0.

Linear search

Inspect candidates sequentially until a match or exhaustion.

Sequential search

Another name for linear search.

Binary search

Search sorted candidates by repeatedly narrowing around a midpoint.

Precondition

A requirement that must hold for the algorithm’s promised behaviour.

Ascending order

Values arranged from smaller to larger, allowing equals.

Candidate

An item or position not yet excluded as a possible match.

Search interval

The remaining candidate range in binary search.

low

The smallest candidate index in this inclusive-boundary version.

high

The largest candidate index in this inclusive-boundary version.

middle

The candidate index calculated for a midpoint probe.

Integer division

Division producing a whole-number quotient for midpoint calculation.

Probe

One inspection of a candidate, such as the midpoint.

Inclusive boundary

A bound whose indexed position belongs to the interval.

Empty interval

No candidates remain; here low > high.

Not-found result

A result indicating absence, chosen as -1 in these functions.

Early return

Ending the current function call before later statements execute.

Duplicate

Another item with the same searched value.

First-match policy

A requirement to return the earliest matching position.

Invariant

A property preserved as the algorithm proceeds.

Termination

Reaching completion instead of continuing indefinitely.

Off-by-one error

A boundary error that includes or excludes one position incorrectly.

Worst case

The greatest work among permitted inputs of the same size.

Indexed access

Access to an item by its position.

Trace table

A structured record of algorithm state, decisions and actions.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which statements about linear search are correct?
2. Which match the Python function result for [18, 7, 25, 4, 12]?
3. Which are required by the shown binary search?
4. For low = 0 and high = 7, which are correct?
5. When values[middle] < target in ascending data, which are correct?
6. Which describe binary-search failure?
7. Which tests expose boundary mistakes?
8. Which statements about duplicates are correct?
9. Which describe search efficiency under the stated assumptions?
10. Which prevent common implementation errors?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Trace linear search for 4 in [18, 7, 25, 4, 12].

2. Construct a linear search returning an index or -1.

3. Explain why binary search requires sorted data.

4. Calculate middle for low = 4 and high = 7 using the shown convention.

5. Trace binary search for 27 in [3, 7, 11, 15, 19, 23, 27, 31].

6. Trace binary search for absent target 20 in the same list.

7. Explain why low <= high is needed for this implementation.

8. Explain why low = middle + 1 is used after a too-small midpoint.

9. Compare the duplicate behaviour of the shown searches.

10. Construct the caller’s logic for retrieving a Python record safely from a search result.

11. Describe a test plan for binary search.

12. Explain why sorting before every single lookup can weaken the case for binary search.

CONSTRUCT IT | STUDENT RECORD RETRIEVAL

Construct a function that searches a list of student records for an exact ID and returns the matching record, or None if absent. The records are stored in arrival order, not ID order. Include caller code that reports an absent record without indexing the collection at -1. State your duplicate-ID policy.

Reveal an approach
def find_student(records, wanted_id):
    for record in records:
        if record["id"] == wanted_id:
            return record
    return None

records = [{"id": 18, "name": "Ada"}, {"id": 7, "name": "Lin"}]
student = find_student(records, 7)
if student is not None:
    print(student["name"])
else:
    print("Student not found")

This linear search preserves arrival order and returns the first matching record. If IDs should be unique, enforce that in the data; the search itself does not establish uniqueness. Returning a record uses a different interface from the earlier index-returning functions.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.4.2 Linear and Binary Search is coming soon. Complete the matching task and written questions in your exercise book.