Binary Search picoCTF 2024 Solution

Description

1. Step 1

   Read the script

   Observation

   I noticed the challenge provided a downloadable guessing_game.sh script alongside the live service, which suggested inspecting it first to understand the exact feedback format (Higher / Lower / Correct) and the 10-guess limit before attempting any live guesses.

   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 guaranteed worst-case bound - you can exhaust all 10 guesses without ever narrowing the range. Reading the script first reveals the exact feedback format (Higher / Lower / Correct) so you know how to use each response to cut the search space in half.

   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. This never overshoots because the floor of the midpoint stays inside [low, high] for any valid range, and feedback always shrinks the range by at least one element. Rounding up could land outside the active range when low and high are adjacent.

2. Step 2

   Halve the range each round

   Observation

   I noticed the challenge description stated 1000 possibilities and only 10 guesses, which suggested that log2(1000) is just under 10 and binary search is the only algorithm that guarantees convergence within that 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 confirmed the current guess is too high, so including it in the next range wastes a guess slot. Setting high = guess - 1 excludes the ruled-out value and keeps the range shrinking by at least one element per step, which is what guarantees termination within 10 rounds.

3. Step 3

   Worked example

   Observation

   I noticed that rounding behavior at each midpoint step was a common source of confusion and potential off-by-one errors, which suggested walking through a concrete target (38) to show exactly how floor division keeps the guess inside the active range at every step.

   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) instead of down (floor) when the sum is odd.

   Using ceiling rounding does not cause infinite loops in most cases but can cause a guess to land outside [low, high] when the two bounds are adjacent (e.g. low=38, high=39 gives midpoint 38.5; ceiling gives 39 which is the wrong half). Floor rounding always stays within the active range and is the conventional safe choice for binary search.

Flag

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