[MS] Finding a specific value in a sequence of integers that changes by at most 1 - devamazonaws.blogspot.com

Consider a sequence of integers with the property that the distance between consecutive values is at most 1. The puzzle is to find a sublinear algorithm for locating a given value, with the condition that the value you're looking for is between the first and last values of the sequence (inclusive).

In formulas,

• x₀, …, xₙ is a finite integer sequence.
• |xₖ − xₖ₊₁| ≤ 1.
• The target integer value v satisfies the property that (xₙ − v)(v − x₀) ≥ 0.

When I saw this puzzle, I thought, "Well, that's obvious."

Look at it this way: Suppose each xₜ represents an object's location at time t = k. The requirement that |xₖ − xₖ₊₁| ≤ 1 means that at each tick, the object can either move left one step (−1), move right one step (+1), or not move at all (0). Since the object can move only in steps, you know that it must eventually reach every integral point between its starting and ending point. (Otherwise, how did it reach its ending point?);

You can think of this as the discrete version of the intermediate value theorem.

Once viewed as a path problem, the solution is clearly to use a binary search. At each step, probe the midpoint xₘ of the range: If it equal to the target value v, then you're done. If it is on the same side of v as x₀, then reduce the interval to xₘ₊₁, …, xₙ. If it is on the same side as xₙ, then reduce the interval to x₀, …, xₘ₋₁. Repeat on the reduced range until you find a hit.

Post Updated on June 24, 2024 at 03:00PM
Thanks for reading
from devamazonaws.blogspot.com