DoAssignment study guide

C2.2 · Compare linear and binary search costs

Learn to compare linear and binary search costs through clear examples and targeted practice.

Ontario Grade 12 Computer Science

Designing Modular Programs

Trace the comparisons, check the input conditions, and make a fair comparison

Searching means looking through a collection for a target value, or determining that it is not present. This lesson builds on familiar Grade 11 ideas: lists, indexes, loops, and comparisons. We will compare the methods by counting each check of one list value against the target. A count from one trace is specific to its list and target; it should not be mistaken for the count in every search.

What you will learn

Describe how linear search and binary search examine a list.
Trace both methods and count value-to-target comparisons.
Compare search costs while recognizing that binary search requires sorted input.

Prerequisite review: lists and comparisons

A list stores values at indexed positions. In Python, the first position has index 0. A search takes a list and a target. Its result can be the index where the target occurs, or a signal that it is absent.

For a consistent cost comparison, count a comparison each time the algorithm checks a list value against the target. For example, testing whether a value equals the target counts as one comparison. Changing an index or choosing which part to search next does not add a value-to-target comparison to this count.

The input condition matters. Linear search can examine values in any order. Binary search depends on the values being sorted, so that their order tells it which part of the list may still contain the target.

Python list indexes begin at 0.
Count checks of list values against the target.
Binary search requires a sorted list.

How the methods search

Linear search starts at the first list value and checks values one at a time. It stops when it finds the target. If it reaches the end without a match, it reports that the target is absent. A target at the first position takes one comparison; an absent target takes one comparison per list value.

Binary search checks the middle value of the remaining part of a sorted list. If it matches, the search is finished. If the target is smaller, the search continues in the lower part; if the target is larger, it continues in the upper part. The method repeats this process until it finds the target or no positions remain.

Each binary-search comparison lets the search discard a part of the remaining list. For a list of length

n

, its comparison count is at most the ceiling of the base-2 logarithm of

n+1

. Linear search uses at most

n

comparisons. These are general upper bounds, not the counts for every particular target.

C_{\text{linear}}\leq n,\quad C_{\text{binary}}\leq\lceil\log_2(n+1)\rceil

Linear search checks in order and can stop at a match.
Binary search repeatedly narrows a sorted search interval.
A trace count depends on the target and its position, or on whether it is absent.

Python 3 methods: input, steps, and expected results

The Python 3 example in the first worked example shows both methods. Each function takes a list named values and a target value. The expected output is the target’s index if found, or -1 if it is absent. The functions are provided for reading and tracing; no claim is made that they were run.

For linear search, visit each index from the beginning, compare its value with the target, and return the index at a match. If the loop reaches the end, return -1. Its precondition is simply that the values can be compared with the target.

For binary search, set the remaining interval to the entire list. While that interval is not empty, find its middle index and compare that value with the target. A smaller middle value means the target, if present, must be to the right; a larger middle value means it must be to the left. If the interval becomes empty, return -1. Its essential precondition is that values are in ascending sorted order.

Both methods take a list and a target and return an index or -1.
Binary search’s narrowing decisions are valid only for sorted input.
Trace the stated code by following its comparisons; do not assume a result without checking.

Comparing costs fairly

A useful comparison gives the list, target, input condition, and number of comparisons for each method. The examples below calculate counts from their exact traces. They are not timing measurements or invented benchmarks.

For a sorted list where a target is far into the list or absent, binary search can use fewer comparisons, as the first two examples show. But linear search may be quicker by this comparison count when the target is at the first position. The third example demonstrates that case.

Do not use binary search on an unsorted list and expect the same narrowing decisions to remain valid. If the list is already sorted, its order supports those decisions. The counts in this lesson compare the searches themselves, not any work that might be needed to prepare input.

Name the input condition and target when reporting costs.
A specific trace count is not a universal count for that list length.
Binary search is not guaranteed to use fewer comparisons for every target.

Worked example

A target found after several checks

Use both methods to find 31 in the sorted list [4, 9, 13, 18, 25, 31, 42, 56, 63]. Count comparisons and report the returned index.

Comparison counts for target 31

For the stated nine-value sorted list: index labels identify the method; values are comparison counts.

Python 3

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

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

Trace linear search
Indexes 0 through 5 are checked in order. The value at index 5 is 31, so the search stops there.
$6$
Trace binary search
The first middle index is 4, containing 25. Since 31 is larger, continue at indexes 5 through 8. The next middle index is 6, containing 42, so continue at index 5. That value is 31, and the search returns index 5.
$3$

Answer: Both methods return index 5. Linear search uses 6 comparisons; binary search uses 3 for this list and target.

Check: The binary-search comparisons are with 25, 42, and 31. The list is sorted, so each narrowing decision is valid.

Worked example

An absent target

Search for 22 in the sorted list [3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47]. Count the comparisons and give the expected result for each method.

Comparison counts for absent target 22

For the stated twelve-value sorted list: index labels identify the method; values are comparison counts.

Python 3

values = [3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47]
target = 22
# Preconditions: values is sorted for binary search.
# Expected result from each search: -1

Trace linear search
The target is absent, so linear search checks each of the twelve values before returning -1.
$12$
Trace binary search
Check index 5, value 23; continue lower. Check index 2, value 11; continue higher. Check index 3, value 15; continue higher. Check index 4, value 19; continue higher. No positions remain, so return -1.
$4$

Answer: Both methods report that 22 is absent. Linear search uses 12 comparisons; binary search uses 4.

Check: The binary-search trace checks 23, 11, 15, and 19. The remaining interval is empty after the fourth check.

Worked example

A match at the first position

Find 2 in the sorted list [2, 6, 10, 14, 18, 22, 26, 30]. Compare the two comparison counts.

Comparison counts for target 2

For the stated eight-value sorted list: index labels identify the method; values are comparison counts.

Python 3

values = [2, 6, 10, 14, 18, 22, 26, 30]
target = 2
# Preconditions: values is sorted for binary search.
# Expected result from each search: index 0

Trace linear search
The value at index 0 is 2, so linear search finds the target and stops after its first comparison.
$1$
Trace binary search
Check index 3, value 14, and continue in indexes 0 through 2. Check index 1, value 6, and continue at index 0. Check 2 at index 0 and return that index.
$3$

Answer: Both methods return index 0. Linear search uses 1 comparison, while binary search uses 3 in this trace.

Check: This case shows why it is inaccurate to claim that binary search always uses fewer comparisons.

Common mistakes and how to avoid them

Using binary search on a list that is not sorted.

Correction: Binary search uses the values' order to decide which part to keep. Use it only when the list is sorted.

Saying that binary search always takes fewer comparisons.

Correction: Compare the actual target and trace. In the first-position example, linear search uses one comparison and binary search uses three.

Treating one trace count as the count for every search of that list length.

Correction: State whether the target is found and where, or that it is absent. Those details affect the count.

Lesson summary

Linear search checks values in order and can work with an unsorted list.
Binary search checks middle values and narrows the interval, but requires sorted input.
Count comparisons from the exact trace and distinguish that count from a general upper bound.

Check your understanding

Question 1

Linear search looks for an absent target in a list of 7 values. How many value-to-target comparisons does it make?

1
3
7
It depends on whether the list is sorted.

Show answer and explanation

The target is absent, so linear search checks all seven values.

Question 2

What condition lets binary search safely narrow its search using the values' order?

The list has an even number of values.
The list is sorted.
The target is at the middle index.
The list has no repeated values.

Show answer and explanation

The list is sorted.

Binary search relies on sorted order to decide which part may still contain the target.

Question 3

Using the middle-first method, how many comparisons are needed to find 5 in the sorted list [5, 10, 15, 20, 25]?

Show answer and explanation

The first check is 15 at index 2. The remaining indexes are 0 and 1; integer division gives middle index 0, where the next check finds 5. The count is 2.

Key terms

Comparison: A check of one list value against the target value.
Linear search: A method that checks list values in sequence until it finds the target or reaches the end.
Binary search: A method for sorted input that checks a middle value and continues in the part that could still contain the target.
Precondition: A condition that must be true before using a method; binary search requires sorted input.

Continue through ICS4U

View the complete ICS4U Ontario Grade 12 Computer Science curriculum and lessons

Tutor support for C2.2 · Compare linear and binary search costs

Working on C2.2 · Compare linear and binary search costs in ICS4U? Bring the question and your own attempt. In a live session, you can trace a small example and find the first step where the output differs from what you expected. Ask about the first step that does not make sense, then try a similar question yourself.

Explore coding tutoring · Request an eligible free 30-minute introduction. Your request is matched by subject and language; a tutor must accept before a time is confirmed.

برای مبحث C2.2 · مقایسه هزینه جست‌وجوی خطی و دودویی در درس ICS4U، سؤال و تلاش خود را همراه بیاورید. در جلسه می‌توانید یک مثال کوچک را دنبال کنید و نخستین گامی را که خروجی با انتظار شما فرق دارد پیدا کنید. راهنمای معلم برنامه‌نویسی را ببینید یا جلسهٔ معارفهٔ رایگان ۳۰ دقیقه‌ای درخواست کنید. زمان جلسه پس از پذیرش معلم قطعی می‌شود.

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 12 Computer Science (ICS4U), expectation C2.2. It is a study resource, not an official curriculum publication.

Before publication, content is checked for structure, mathematical or chemical notation, calculations, course boundaries, and readability. Errors can still occur, so corrections are welcomed.

Official curriculum reference

Report a correction or ask a question