DoAssignment.ca

DoAssignment study guide

A3.2 · Linear and Binary Search: Trace and Compare

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

Ontario Grade 12 Computer Science

Programming Concepts and Skills

ICS4U A3.2: finding a value in a list

Searching means checking a collection for a particular value, called the target. In this lesson, the collection is a list and the result is either the target's index or an indication that it is absent. ICS3U experience with lists, indexes, comparisons, loops, and selection is enough to follow both methods. Linear search can use a list in any order. Binary search can be used only when the list is sorted. The key task is to choose a method whose input conditions are met, then trace its comparisons carefully.

What you will learn

  • Describe the input conditions and steps for linear search.
  • Write a linear search that reports whether a target is present and where it is found.
  • Explain why binary search needs a sorted list and how each comparison narrows the search.
  • Trace linear and binary search and report their comparison counts for a given example.

1. Prerequisite review: lists, indexes, and results

A list stores values in positions called indexes. In Python, indexes begin at 0, so a list with five items has indexes 0 through 4. A search compares a target with values at these positions. A successful search can return the index where the target occurs; an unsuccessful search needs a distinct result, such as -1, to mean that no matching index was found.
Before writing a search, identify its input and expected result. Here the inputs are a list and a target. The output is the index of a matching item, or -1 if there is no match. For binary search, add an essential precondition: the list must already be sorted in ascending order. Sorting is not part of either search procedure in this lesson.
  • Python list indexes begin at 0.
  • Choose a clear not-found result, such as -1.
  • Binary search requires values in ascending order.

2. Linear search: check items in order

Linear search starts at the first item and compares each item with the target. If they match, return that item's index. If they do not match, continue to the next index. When every item has been checked without a match, return -1. The method does not rely on the list being sorted.
A loop index provides a direct way to visit each position once. The loop condition keeps the index within the list. The equality test checks for a match; increasing the index after a mismatch ensures the next comparison is with the next item. If the list is empty, the loop has no iterations and the method returns -1.
When a target appears more than once, this version returns the first matching index because it stops as soon as it finds a match. State this behaviour when describing the result.
  • Start at index 0 and move forward one position after each mismatch.
  • Return immediately when the target matches.
  • If the loop finishes, the target was not found.

3. Binary search: narrow a sorted list

Binary search keeps track of the part of a sorted list where the target could still be. Begin with the first and last indexes. Find the middle index and compare the middle value with the target. If they match, return the middle index. If the target is smaller, continue with the portion to the left; if larger, continue with the portion to the right.
After choosing a side, move the corresponding boundary past the middle index. This matters because the middle value has already been checked: it cannot be the target if the comparison was unequal. Repeat while the left boundary is no greater than the right boundary. If the boundaries cross, no unchecked candidate positions remain, so return -1.
The input must be sorted in the same order assumed by the comparisons. With ascending order, a value smaller than the middle value can only be to its left, and a larger value can only be to its right. On an unsorted list, that reasoning is not valid, and binary search can miss a value that is present.
m=⌊left+right2⌋m = \left\lfloor\frac{\text{left} + \text{right}}{2}\right\rfloor
  • Set the initial search range to the full list.
  • Compare with the middle item and discard the middle plus the impossible side.
  • Stop with -1 when the search range becomes empty.

4. Compare methods and check the conditions

Linear search is the suitable choice when the list may be in any order or when its order is not known to be sorted. Binary search takes advantage of sorted order to remove a portion of the remaining candidates after each unequal middle comparison. Both methods should be checked against the same target and list when comparing their traces.
A comparison count is the number of times a list value is tested against the target. It depends on the particular list and target. The counts in the examples are exact counts for those traces, not measured performance claims. In either method, a successful search can stop as soon as it finds a match.
For your own trace, write down the index checked at each step. For binary search, also record the current left and right boundaries. This makes it easier to see whether each update preserves only positions that could still contain the target.
  • Linear search has no sorted-input requirement.
  • Binary search is correct only when the list is sorted as required.
  • Trace actual comparisons rather than guessing a count.

Worked example

Linear search finds a target

Use linear search on [14, 6, 21, 9, 17] to find 9. Give the returned index and number of comparisons. The list may be unsorted.
Linear search trace
Index → stored value0141622139: match417

Each value is checked from left to right; the target is found at index 3.

Python 3

def linear_search(items, target):
    for index in range(len(items)):
        if items[index] == target:
            return index
    return -1
  1. Set up the search
    The input list is [14, 6, 21, 9, 17] and the target is 9. Linear search needs no sorted-order precondition. Start at index 0 and compare each value in turn.
  2. Trace the comparisons
    At index 0, 14 is not 9. At index 1, 6 is not 9. At index 2, 21 is not 9. At index 3, 9 matches, so stop rather than checking index 4.
  3. Report the result
    The target is at index 3. Four list values were compared with the target, so this trace uses four comparisons.
Answer: Index 3; 4 comparisons.
Check: The trace checks indexes 0, 1, 2, and 3, and stops at the first match.

Worked example

Linear search reports an absent target

Use the same linear-search method on [5, 12, 8, 20] to find 7. Give the returned result and number of comparisons.
Full linear search trace
Index → stored value0511228320

Every item is checked; none matches the target 7.

Python 3

def linear_search(items, target):
    for index in range(len(items)):
        if items[index] == target:
            return index
    return -1
  1. Set up the search
    The input list is [5, 12, 8, 20] and the target is 7. No sorted order is needed. Since the target may be absent, keep checking until either a match is found or the list ends.
  2. Check every item
    Index 0 contains 5, index 1 contains 12, index 2 contains 8, and index 3 contains 20. None equals 7. All four items have therefore been compared.
  3. Return the not-found value
    The loop has no more list positions to check. Returning -1 communicates that the target was not found; it is not an index in this list.
Answer: Return -1; 4 comparisons.
Check: All four values are checked exactly once, and none matches 7.

Worked example

Binary search in a sorted list

Use binary search on the ascending list [3, 8, 12, 19, 24, 31, 40] to find 24. Give the returned index and number of comparisons.
Binary search trace
Index → stored value0318212319: compare 1424: compare 3, match531: compare 2640

The sorted list is narrowed from indexes 0–6 to 4–6, then 4–4.

Python 3

def binary_search(items, target):
    left = 0
    right = len(items) - 1
    while left <= right:
        middle = (left + right) // 2
        if items[middle] == target:
            return middle
        if target < items[middle]:
            right = middle - 1
        else:
            left = middle + 1
    return -1
  1. Check the precondition
    The list is in ascending order, so binary search is appropriate. Set left to index 0 and right to index 6. The target is 24.
  2. Compare at the middle
    The middle index is 3, whose value is 19. Since 24 is greater than 19, the target, if present, must be to the right. Set left to index 4.
  3. Search the remaining range
    The range is now indexes 4 through 6. Its middle index is 5, whose value is 31. Since 24 is less than 31, set right to index 4.
  4. Find the target
    The remaining range contains only index 4. Its value is 24, so return index 4. The trace made three comparisons: with 19, 31, and 24.
Answer: Index 4; 3 comparisons.
Check: The comparison values are 19, 31, and 24. Each boundary update keeps the target's index in the remaining range.

Common mistakes and how to avoid them

Using binary search on a list that is not sorted.
Correction: Use binary search only when the list is sorted in the order expected by its comparisons. Otherwise, use linear search.
Moving a binary-search boundary to the middle index after an unequal comparison.
Correction: The middle item has already been checked. Exclude it by setting the boundary to middle - 1 or middle + 1.
Returning an index for an absent target.
Correction: Return the chosen not-found value, such as -1, after all possible positions have been checked.
Counting positions instead of comparisons.
Correction: Count each time the algorithm compares a list value with the target. Stop counting when a match ends the search.

Lesson summary

  • Linear search checks list items from the beginning and works whether or not the list is sorted.
  • Binary search compares at the middle of a sorted list and continues only in the side that could contain the target.
  • Both methods should return a matching index or a clearly defined not-found result.
  • A trace should show the checked values and, for binary search, the changing search boundaries.

Check your understanding

Question 1

Which search method can be used on an unsorted list without changing the list first?
  1. Binary search, because it always checks the middle.
  2. Linear search, because it can check every item without relying on order.
  3. Either method, because order does not affect the comparisons.
  4. correctIndex":1,"explanation":"Linear search checks items in sequence and does not depend on sorted order. Binary search needs sorted input."}
Show answer and explanation
Linear search, because it can check every item without relying on order.
Linear search checks items in sequence and does not depend on sorted order. Binary search needs sorted input.

Question 2

For binary search on [2, 6, 11, 15, 22], the target is 18. The first middle value is 11. Which indexes remain possible after that comparison?
  1. Indexes 0 through 2
  2. Indexes 3 through 4
  3. Only index 2
  4. correctIndex":1,"explanation":"The list is ascending and 18 is greater than 11, so only values to the right of index 2 can contain it: indexes 3 and 4."}
Show answer and explanation
Indexes 3 through 4
The list is ascending and 18 is greater than 11, so only values to the right of index 2 can contain it: indexes 3 and 4.

Question 3

A linear search checks [10, 4, 13, 7] for 13. What index does it return, and how many comparisons does it make?
  1. Index 2; 3 comparisons
  2. Index 3; 4 comparisons
  3. -1; 4 comparisons
  4. correctIndex":0,"explanation":"The values at indexes 0, 1, and 2 are compared in order. The third comparison finds 13 at index 2."}
Show answer and explanation
Index 2; 3 comparisons
The values at indexes 0, 1, and 2 are compared in order. The third comparison finds 13 at index 2.

Key terms

Target
The value a search is trying to find.
Index
The numbered position of an item in a list; Python indexes start at 0.
Precondition
A condition that must be true for an algorithm to be used correctly; binary search requires sorted input.
Comparison
A check of whether a list value equals, is less than, or is greater than the target.

Continue through ICS4U

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

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 12 Computer Science (ICS4U), expectation A3.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