Session 4 How many questions? Search Algorithms

Published

June 14, 2026

Problem: Guess a letter A–Z using yes/no questions; why is 5 questions the minimum, not 4 or 6?
Generalisation: If the answer is between 1 and 100, 1 and 1000, or 1 and (n), how many yes/no questions are needed?

Linear Search vs Binary Search

Linear (simple) search: Check each option one by one: “Is it A? Is it B? Is it C?” etc.
For 26 letters, worst case is 26 questions; for 100 items, worst case is 100 questions.
Binary search: Each question halves the remaining possibilities (decision tree: 1–50, then 1–25, 1–12, 1–6, 1–3, 1–2, etc.).
For 100 items, worst case is 7 questions (because (2^7 = 128), which is the first power of 2 ≥ 100).

Pattern:
1 question → up to (2^1 = 2) items
2 questions → up to (2^2 = 4) items
3 questions → up to (2^3 = 8) items
In general: (n) questions → up to (2^n) items.
Inverse view: For a given number of items, questions needed ≈ log base 2 of (number of items).
Log definition: If (x^n = m), then (_x m = n).
Example: (2^3 = 8 2 8 = 3); (10^2 = 100 {10}100 = 2).
Binary search runs in logarithmic time: number of questions grows slowly even when items grow a lot (e.g. 1000 items need 9 questions, 10,000 need 14).

Binary search only works on sorted (ordered) lists (e.g. numbers in increasing order, names in alphabetical order).
If data is unsorted (like ), you must either:
Use linear search, or
First sort the data, then use binary search.
Searching is a very common and expensive operation in computing (e.g. Facebook finding your username among millions/billions quickly).
Because of this, sorting becomes a key problem in computer science: given items, arrange them into a sorted order.

Setup: One 5‑litre jug and one 3‑litre jug; you must measure specific amounts of water (e.g. 2L, 4L, 1L).
Example solutions:
To get 2L: Fill 5L, pour 3L into the 3L jug, 2L remains in the 5L jug.
To get 4L efficiently: Use a smarter sequence of pours (e.g. use the 3L jug twice so only two measurements are needed).
Key idea: There can be many algorithms (step sequences) to solve the same problem; we care about the one with fewest operations.

Setup: 3 coins, one fake coin which is lighter, and a balance scale that only tells which side is heavier or if they’re equal.
This gives 3 outcomes per weighing: left heavier, right heavier, or equal.
With 3 coins and 1 lighter fake coin:
Weigh two coins once; from the result (heavier, lighter, equal), you can identify the fake in just 1 weighing.
Extended problem: 9 coins, 1 lighter fake coin:
Naive strategy (pairwise weighing) can take up to 4 weighings.
Better strategy:
Put 3 coins vs 3 coins, keep 3 aside (ternary split).
One weighing narrows you to 3 suspect coins; second weighing finds the fake.
So 9 coins can be solved in 2 weighings.
General pattern:
1 weighing → handle 3 coins
2 weighings → handle (3^2 = 9) coins
3 weighings → handle (3^3 = 27) coins, by repeating the same splitting into groups of three.
This idea is like a ternary search (splitting into 3 parts), while binary search splits into 2.

An algorithm is a precise sequence of steps to solve a problem; it is not tied to any specific computer or programming language.
Each action (question asked, pour done, weighing performed, comparison made) counts as one operation and takes time.
Typical development flow:
Algorithm (high‑level idea).
Pseudocode (steps written in simple, computer‑like language).
Actual program (e.g. C printf(...) or Python print(...)).
Modern AIs can often write code, but you still need the algorithm and reasoning, especially for new or unfamiliar problems.

Understanding exponents and logarithms is important because many algorithms, like binary search, are described and analysed using these ideas.
Logs convert exponential growth (like (2^n)) into a manageable linear scale ((n)), which helps in thinking about efficiency.