Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 8
Searching (Lecture 08)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
Which search works on an unsorted list?
The other three all rely on the order to skip elements.
-
The largest number of comparisons binary search makes on a sorted list of 1,000 elements is:
⌊ log2 1000 ⌋ + 1 = 9 + 1 = 10. 1,000 (a) is linear search's worst case.
-
…and on 1,000,000 elements:
⌊ log2 106 ⌋ + 1 = 19 + 1 = 20.
-
Binary search is called on a list that is not sorted. It:
Nothing checks the order — checking would cost O(n). The comparison with the middle then discards the wrong half, and a value that is present can be reported as −1.
-
binary_search(V, 20): the index of the first element compared is:mid = (0 + 15) // 2 = 7,V[7] = 24. -
…and the index of the second:
24 > 20, so
hi = 6;mid = (0 + 6) // 2 = 3,V[3] = 12. -
The loop invariant of binary search is:
It is what makes "the range is empty" mean "the target is not there".
-
A binary search with an inclusive
hiloopswhile lo < hi. Searching[42]for 42, it returns:With
lo = hi = 0the loop never runs, so the only candidate is never compared (W8-B1). -
In Java,
mid = (lo + hi) / 2is a bug because:Joshua Bloch's 2006 bug report: arrays of more than about 230 elements. Fix:
lo + (hi - lo) / 2. Python integers do not overflow. -
A recursive binary search calls itself on
values[:mid]orvalues[mid + 1:]. Its total time on n elements is:The slices copy n/2 + n/4 + … < n elements in total (W8-K2).
-
The extra space of
binary_search_recursive(passingloandhi, no slices) is:One frame per halving: about log2 n frames. The loop form is O(1) (a).
-
lower_bound([1, 2, 2, 2, 5, 7], 2)is:The first index with
v[i] >= 2. -
upper_bound([1, 2, 2, 2, 5, 7], 2)is:The first index with
v[i] > 2: the 5 at index 4. -
lower_bound([1, 2, 2, 2, 5, 7], 8)is:No element is ≥ 8, so the answer is
len(v)= 6 — the insertion point at the end. The bounds never return −1 (a). -
How many times does 3 occur in
[1, 3, 3, 3, 3, 9], computed asupper_bound(v, 3) - lower_bound(v, 3)?upper_bound= 5 andlower_bound= 1: 5 − 1 = 4. -
Python's
bisect.bisect_left(values, x)is the same as:And
bisect_rightisupper_bound. -
Jump search on 100 sorted elements jumps by:
√(100) = 10: at most 10 jumps and 10 steps inside a block.
-
Jump search uses blocks of size √n because:
n/m + m is smallest at m = √n, giving 2√n. Jump search is O(√n), not O(log n) (d).
-
Exponential search for a target at index 11 of a 32-element list checks the bounds:
It checks slot 0, then doubles:
v[16]is the first bound not smaller than the target, and binary search runs on slots 8 to 16. -
Exponential search is most useful when:
Doubling needs no end, and it costs O(log i) for a target at index i.
-
The worst case of interpolation search is:
One huge value makes every guess land at the left end, and the range shrinks by one per step (W8-T5).
-
Interpolation search on
[10, 20, 30, …, 100](10 values) for 70: the first index it probes is:0 + (70 - 10)(9 - 0) / (100 - 10) = 540 / 90 = 6, and
v[6] = 70: found in one probe.
18 marks
Written questions
5 written questions (18 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 18
-
Describe binary search. State its loop invariant and use it to explain why the algorithm is correct, and show that it makes at most ⌊ log2 n ⌋ + 1 comparisons. What must the caller guarantee?
Model answer and marking points
- Algorithm: keep
lo = 0,hi = n − 1; whilelo <= hi, compare the target withvalues[mid],mid = (lo + hi) // 2: equal → returnmid; smaller middle →lo = mid + 1; larger →hi = mid − 1. Return −1 when the range is empty. - Invariant: if the target is in the list, it is in
values[lo..hi]. True at the start (whole list); each step removes only elements that the sorted order proves cannot be the target; so when the range is empty, the target is absent — the −1 is correct. - Count: each unsuccessful comparison leaves at most half the range; after ⌊ log2 n ⌋ halvings one element is left, and one more comparison settles it: O(log n).
- Caller's guarantee: the list is sorted (a precondition — not checked).
- Algorithm: keep
-
Give four classic bugs in binary search. For each, give an input on which it fails, what happens, and the fix.
Model answer and marking points
while lo < hi(inclusivehi): the last candidate is never compared —[42]searched for 42 gives −1. Fix:lo <= hi.hi = mid: when the range is one element and it is too big, nothing changes —[1, 3]searched for 0 loops for ever. Fix:hi = mid − 1.lo = mid: withlo = 0, hi = 1andvalues[0]too small,midstays 0 — loops for ever. Fix:lo = mid + 1.mid = (lo + hi) / 2in Java/C: overflows on arrays over about 230 elements, giving a negative index. Fix:lo + (hi − lo) / 2.- (Also accepted: recursing on slices — returns an index into the slice, W8-B3.)
-
Define
lower_boundandupper_bound. Give three uses of them, and explain why they never return −1.Model answer and marking points
lower_bound(v, x): the first index i withv[i] >= x;upper_bound(v, x): the first withv[i] > x. Both in O(log n), on a sorted list.- Uses: the insertion point that keeps the list sorted (
lower_bound); the number of copies of x (upper_bound − lower_bound); the first occurrence (lower_bound, then checkv[i] == x); the count of values in[a, b). - Never −1: they answer "where", not "whether" — every x has a position in the order, from 0 (before everything) to
len(v)(after everything). That is why the search range is half-open,[0, len(v)):len(v)must be a possible answer. - Python:
bisect_leftandbisect_right.
-
Compare jump search, exponential search and interpolation search: cost, and a situation in which each is the right choice.
Model answer and marking points
- Jump, O(√n): moves only forward, in blocks of √n — for storage where going back is expensive (tape, a stream read in order).
- Exponential, O(log i) for a target at index i: doubles a bound, then binary searches — for sequences of unknown length, or targets near the front.
- Interpolation, O(log log n) on average for evenly spread values but O(n) in the worst case: guesses the position from the values — for large, uniformly distributed keys (numeric IDs, timestamps) where you can trust the distribution.
-
A program searches an unsorted list of n values k times. When is it worth sorting the list first? Compare the costs, and give a concrete example with n = 1,000,000.
Model answer and marking points
- Linear search k times: O(kn). Sort once and binary search k times: O(n log n + k log n).
- Sorting pays once kn > n log n, i.e. once k exceeds about log2 n.
- Example: n = 1,000,000. One linear search: up to 10^6^ reads. Sorting: about n log2 n ≈ 2 × 107 comparisons, then 20 per search. After about 20 searches the sort has paid for itself.
- If the data also changes often, a sorted array's O(n) insertion is the catch: a balanced search tree (Week 11) or a hash table (Week 13) may fit better.