Binary Search picoCTF 2024 Solution

Description

1. Step 1Read the script

   Observation

   The challenge ships guessing_game.sh next to the live service. Read it first so you know the exact feedback wording and the 10-guess limit before spending a guess.

   The provided guessing_game.sh gives you 10 guesses and tells you whether the target is "Higher" or "Lower" than each guess.

   What didn't work first

   Tried: Skipping the script and just guessing numbers at random on the live service.

   Random guessing has no worst-case bound: you can burn all 10 guesses without narrowing anything. Reading the script shows the exact feedback wording, which is what lets each response halve the search space.

   Tried: Trying to read the script to find the hardcoded target number so the first guess is always correct.

   The target is generated with $RANDOM at runtime, so no static value is embedded in the script. The script is useful for understanding the feedback protocol and the 10-guess limit, not for extracting the answer directly.

   Learn more

   Binary search assumes a sorted range and halves it on each comparison. Starting with N candidates, after k guesses you have at most ceil(N / 2^k) candidates left. For N = 1000, log2(1000) is approximately 9.97, so you need at most 10 guesses to guarantee a hit, which is exactly the budget the service gives you.

   Round 0.5 downward (floor division) when picking the midpoint. Floor keeps the guess inside [low, high] for any valid range, and because each response moves a bound past the guess, the range shrinks by at least one element every round. Ceiling would also terminate here; floor is simply the conventional choice, and it is the one that keeps the guess from creeping toward high when the bounds are adjacent.

2. Step 2Halve the range each round

   Observation

   There are 1000 possibilities and 10 guesses. Since log2(1000) is just under 10, binary search is the only approach that fits the budget.

   Start at the midpoint of the current range. If the service says Lower, the target is below your guess; set high = guess - 1. If Higher, set low = guess + 1.

   Formula:(low + high) / 2(always round 0.5 downward)

   What didn't work first

   Tried: Trying linear search - starting at 1 and incrementing by 1 each guess.

   Linear search needs up to 1000 guesses in the worst case. With only 10 guesses allowed, this runs out after reaching 10, nowhere near the target. Binary search is the only strategy that fits within the 10-guess budget.

   Tried: After a Lower response, updating the range to high = guess instead of high = guess - 1.

   The service already ruled that value out, so keeping it in the range wastes a guess. Setting high to guess - 1 drops it and keeps the range shrinking by at least one element per step, which is what guarantees finishing in 10 rounds.

   Learn more

   The guess budget is not arbitrary. Each round you compare against the midpoint, and whichever answer comes back discards everything on one side of it, so the number of candidates still in play is at most halved. Starting from 1000, the sizes fall 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1: ten halvings, which is why the limit is exactly 10 rather than a round number chosen for looks. In general a range of n needs ceil(log2(n)) guesses, and 2 to the 10th is 1024, comfortably above 1000.

   The rounding direction matters more than it looks. Using floor division for the midpoint means the guess is always a value actually inside the current range, never one past its top. Combined with excluding the guess itself when you narrow (high = guess - 1 rather than high = guess), that guarantees the range shrinks by at least one element every round. Drop either detail and the search can stall on a two-element range, revisiting the same value until the budget runs out.

3. Step 3Worked example

   Observation

   Rounding at the midpoint is where off-by-one errors creep in. Walking through a concrete target, 38, shows how floor division keeps every guess inside the active range.

   If the target is 38, the search converges in seven guesses. Each row shows the midpoint, the response, and the next active range.

   1. Step 1too high

      Guess: 500

      (1 + 1000) / 2 = 500.5 -> 500 (round down)

      Next range: 1 - 499

   2. Step 2too high

      Guess: 250

      (1 + 499) / 2 = 250

      Next range: 1 - 249

   3. Step 3too high

      Guess: 125

      (1 + 249) / 2 = 125

      Next range: 1 - 124

   4. Step 4too high

      Guess: 62

      (1 + 124) / 2 = 62.5 -> 62 (round down)

      Next range: 1 - 61

   5. Step 5too low

      Guess: 31

      (1 + 61) / 2 = 31

      Next range: 32 - 61

   6. Step 6too high

      Guess: 46

      (32 + 61) / 2 = 46.5 -> 46 (round down)

      Next range: 32 - 45

   7. Step 7flag found

      Guess: 38

      (32 + 45) / 2 = 38.5 -> 38 (round down)

      The service reveals the flag once the exact value is submitted.

   What didn't work first

   Tried: Rounding the midpoint up (ceiling) while updating the bound to high = guess instead of high = guess - 1.

   That pairing can stall: with low 38 and high 39 the midpoint 38.5 rounds up to 39, and a Lower response that sets high = 39 leaves the range unchanged, so the same guess repeats until the budget runs out. Flooring the midpoint and moving the bound past the guess shrinks the range by at least one element every round.

Flag

After the correct guess, the service prints the flag as a visible string in the same shell session.