Binary Search related question — O(n) with conditions

by

In a game, your objective is to guess a number from the range 1 to n. You are allowed to make a maximum of ⌈log n⌉ guesses per round. Over the course of m rounds (where m < n), you record the correct answers in an array M[i], with i starting from 1 to m. Initially, designing an algorithm that runs in O(m*log(n)) time is straightforward.
However, a new condition has been introduced: M[i] ≤ M[j] for all i > j, which means the answers are in descending order. The task is to find an algorithm that operates in O(n) time, given this modified condition.

Based on the condition M[i] ≤ M[j] for all i > j, I can narrow down the range between 1 to n. But in the worst case, I still cannot get O(n).
Also, you cannot brutal force to guess the numbers, there is a limit on it.

Some clarifications:
1.When you guess, you are told it’s too large or too small. (it’s a classic binary search question)
2.The answers are in a descending order.
3.The limit of guessing times in each round is ⌈log n⌉, not log(n) + 1, sorry for my mistakes in the previous statement.

Let me give an example, hope this helps.

  • Let’s play a game, you need to guess an integer from 1 to 100 (n = 100).
  • You need to play it 10 rounds (m = 10).
  • In each round, you have ⌈log n⌉ guesses. I will tell you if your answer is too big or too small.
  • The answer in next round is always equal to or less than previous round. Such as: {98,88,76,76,76,74,65,43,43,42}

Let me know if you need more info.

Thanks in advance!

  • 2

    When you guess, are you just told whether or not you’re correct, or are you told whether your wrong guess is too large or too small?

    – 

  • Are the answers in a descending order, or are they in a non-ascending order?

    – 




  • If you are still limited to log_2(n)+1 guesses in each round, then I don’t think this is possible. If you aren’t then it’s easy — always guess the highest possible answer.

    – 

  • I don’t think the question is well formed. If m is part of the input, there must be m in your time, since just reading that input takes time log(m). In this case, you even have to write the m answers, so you need time at least O(n+m)

    – 




  • When you guess, you are told it’s too large or too small.

    – 

Inputs:

  • n: an integer
  • M: a nonincreasing array of integers in the range 1-n, with 1 as the first index. |M| = m < n.

Goal: recreate M in sequence by making at most ⌈log n⌉ guesses per index, with a running time of O(n).

Notation:

  • Let k = ⌈log n⌉, our max guesses per index.
  • Let M’ be the output array. Unlike the input array, for convenience this will be zero-indexed, with M'[0] = n. Our goal will be to have M'[i] = M[i] for 1 <= i <= n.

Procedure to determine M[i] given M[i-1]:

  • guess 1: M[i-1] – k + 1
  • case 1: If our first guess is correct, we’re done.
  • case 2: if our first guess is too small, the correct answer is one of the k-1 values between M[i-1] and M[i-1] – k + 2 inclusive. We will guess these in descending order.
  • case 3: if our first guess is too large, the correct answer is between 1 and M[i-1] – k inclusive. We use binary search to determine the correct answer in at most k-1 additional steps, for a total of k.

First Constraint Analysis: guess each number in at most k = ⌈log n⌉ steps.

case 1 steps: 1

case 2 steps: M[i] – M[i-1] + 1 <= k

case 3: I claim without proof that binary search will take at most ⌈log n⌉ – 1 steps in the range 1 to n – ⌈log n⌉. Let me know if you need a formal proof. Given that, this takes at most k steps (the initial guess, plus at most k-1 for binary search).

So this satisfies the first constraint, that each number is guessed in at most k steps.

Second Constraint Analysis: The algorithm should be O(n).

Let’s say G[i] is the number of guesses we make to determine M[i]. Note that for all three cases, G[i] <= M[i-1] – M[i] + 1. In other words, if successive values of M differ by r, we will determine the latter value in at most r+1 guesses (never more than k, but we don’t need that fact for this portion).

But the cumulative difference across all of M is at most n-1, and |M| < n, so the total number of guesses must be <= (n-1) + |M| < (n-1) + n = 2n-1 = O(n).

Leave a Comment