SME
Data Structures & Algorithms
Sorting and searching
Use this for “At most how many comparisons does binary search make in a sorted list of 1000?”
Diagram
Binary search: ⌊log₂ 1,000⌋ + 1 = 10 comparisons at most, one per halving.
Linear search: up to 1,000, 500.5 on average.
This is an example. Type your own values to start a new problem.
Cb
=
⌊log₂
n
⌋
+
1
k
Halvings
worked out (not typed)
Cₗ
Linear search, worst case
worked out (not typed)
C̄ₗ
Linear search, average
worked out (not typed)
Formulas
k
=
⌊log₂
n
⌋
9 = ⌊log₂ 1,000⌋
Cb
=
k
+
1
10 = 9 + 1
Cₗ
=
n
1,000 = 1,000
C̄ₗ
=
n
+ 1
2
500.5
=
1,000 + 1
2
Assumptions
•
The list is sorted, and each comparison of the target with one item counts as one step.
•
Binary search halves the range left after each comparison; linear search checks items in order.
•
Linear search’s average assumes the target is in the list, equally likely at any place.
Step-by-step
WE KNOW
n = 1,000
FIND
halvings (k), binary search, worst case (Cb), linear search, worst case (Cₗ), linear search, average (C̄ₗ)
Step 1 · Find halvings (k)
Use k = ⌊log₂ n⌋
Halving
n
items
k
times
leaves
one
item
when
2ᵏ
≤
n
<
2ᵏ⁺¹.
⌊log₂
1,000⌋
=
9,
since
2
9
=
512
≤
1,000
<
1,024
=
2
10
k
=
9
Step 2 · Find binary search, worst case (Cb)
Use Cb = k + 1
Each halving costs one comparison, and one more checks the last item left.
Cb = 9 + 1
Cb = 10
Step 3 · Find linear search, worst case (Cₗ)
Use Cₗ = n
In the worst case the target is last or missing, so linear search checks every item.
Cₗ = 1,000
Step 4 · Find linear search, average (C̄ₗ)
Use C̄ₗ = (n + 1) ÷ 2
The
target
is
equally
likely
at
places
1
to
n
,
so
the
average
is
1 + 2 + … +
n
n
.
C̄ₗ
=
1,000 + 1
2
C̄ₗ
=
1,001
2
C̄ₗ = 500.5
Check
Put the numbers back in. Both sides should match.
9 = ⌊log₂ 1,000⌋ ✓
10 = 9 + 1 ✓
1,000 = 1,000 ✓
500.5
=
1,000 + 1
2
✓
← Previous lesson
Preorder traversal of a search tree
Next lesson →
Comparisons: quadratic sorts vs merge sort
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Comparisons: quadratic sorts vs merge sort
Use this for “How many comparisons does selection sort make on 1000 items, and at most how many does merge sort make?”
Hash table probes
Use this for “750 keys sit in a hash table of 1000 slots. How many probes does a search take on average?”
Merge sort pass by pass
Use this for “Show the passes of merge sort on 5 2 8 1 9 3 7 4. How many comparisons does it make?”