Tutorial 3: Problem-Solving Strategies: Sorting and Searching

Unit 2 ยท Section 3

Objectives

Linear search checks items sequentially and works on unsorted data. Binary search repeatedly halves a sorted search range. Sorting has an upfront cost, so choose it when repeated queries justify that cost.

binarySearch(sorted, target):
    low = 0; high = length - 1
    while low <= high: inspect middle and discard half

Exercises

  1. Trace binary search for a target.
  2. Compare repeated linear searches with sort-then-search.
  3. State the precondition for binary search.

Self-check

  1. What must binary search assume?
  2. What is a search range?
  3. Why sort once?

Self-Check Quiz

1. What is binary search's typical growth?

Answer$O(\log n)$ comparisons on sorted data.

2. What happens if data is unsorted?

AnswerBinary search's discard-half reasoning is invalid; use linear search or sort first.

Homework

  1. Implement and test linear and binary search.
  2. Count comparisons for best and worst cases.
  3. Explain which strategy fits a changing dataset.
Sample answerLinear search needs no ordering and is suitable for small or frequently changing data. Binary search requires sorted data but scales better for repeated lookup; tests include first, last, absent, empty, and duplicate targets.