Finding a specific value in a sequence of integers that changes by at most 1
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.
Light
Dark
7 comments
I think you’re assuming the series is monotonically changing. That’s not the problem as you stated it.
What does your algo do with this sequence: 1, 2, 3, 2, 1, 2, 2, 2, 2, 1 with target 3?
First pick the middle. The value is 1, which is to the left of 3, so go right . . . but then you won’t find the 3 because it’s in the left subseries.
—–
I think instead that the not-clearly stated thing is that whatever sample you choose, if it’s not the target then the target is no less than |choice_value – target_value| away, so you can skip to hat many away before taking your next sample in whichever direction you’re headed.
I’d just start at index 0 (because I’m simple) and hop/skip/jump my way up. In my stupid example, that finds 3 on the second step. I didn’t mean to make the example do that – I was just trying to show how your algo didn’t work. 😉
At any rate, it will find the value and it will be sublinear because of all the hopping.
Please remove the last element in my sequence. Typo which threw everything off. My points are still ok, I think.
Devblogs allows you to edit your own comments. You should see a pen icon in the top-right corner of each comment you posted as long as you’re logged in.
One of the puzzle conditions is “the value you’re looking for is between the first and last values of the sequence (inclusive),” so in your sample sequence “1, 2, 3, 2, 1, 2, 2, 2, 2”, the target value would have to be 1 or 2, not 3.
“1, 2, 3, 2, 1, 2, 3, 2, 3, 4” satisfies all the conditions that were given. Now how do you find 3?
It doesn’t matter what the rounding algorithm is, so let’s just say we round down if there are an even number of elements remaining. There are 10 elements to start, so the midpoint is the fifth element, which is 1. That is too low, so focus on elements 6 to 10. The midpoint of that is element 8, whose value is 2. Still too low, so focus on elements 9 and 10. The midpoint element is number 9, whose value is (yay) 3.
Left = -Right.