Is this ordinary linear array search?

No. It concerns an unknown target location along a line.

Does doubling always travel nine times the direct distance?

No. Nine is the standard worst-case ratio, and many targets cost much less.

Can randomization change the result?

Yes. Randomized strategies are assessed using expected cost under specified adversary assumptions.

AI Glossary / Mathematics and optimization / Intermediate

Linear search problem

Definition

The linear search problem studies how to find a target at an unknown location on a line when a searcher starts at a known point and does not know which direction to take. In its classic online form, performance is measured by total distance traveled relative to a searcher who knows the target location. It is also called the two-direction cow-path problem.

What it means

This term does not mean scanning entries in an array or choosing a step length during numerical optimization. The searcher physically or conceptually explores an unbounded line, learns that an explored segment does not contain the target, and decides how far to go next.
A useful strategy must eventually reach any finite target on either side. Going forever in one direction fails if the target is on the other side. Repeatedly inspecting only a fixed short interval also fails for a distant target.

How it works

Normalize a known positive lower bound on the target's distance to one unit. A classic deterministic strategy explores distances 1,2,4,8,16 and so on from the origin, alternating directions and returning to the origin after each unsuccessful excursion. Stop immediately when the target is encountered.
An informed offline searcher would travel directly to the target, a distance d. Competitive analysis compares the online travel with d in the worst case. The doubling strategy has ratio at most 9 under the standard assumptions, and 9 is the optimal deterministic competitive ratio. Different information, randomization, detection rules, or movement costs define different problems.

Three practical examples

A robotics-theory exercise can model searching along a straight corridor when a target's direction is unknown and detection occurs upon reaching it.
An online-algorithm course can use the problem to compare decisions made without future information with an informed benchmark.
A planning simulation can examine the cost of alternating exploration when only a distance scale and a two-direction search space are known.

Think of it this way

Think of standing on a straight path looking for an unmarked destination that may be left or right. Each unsuccessful trip teaches you where it is not, so the next trips must reach farther. The analogy assumes the target remains fixed and detection is reliable; actual search environments may violate both assumptions.

Worked example

Consider an original doubling schedule starting to the right. The planned farthest positions on successive excursions are +1,-2,+4,-8,+16, measured from the origin. Unsuccessful excursions return all the way to zero. The target is at -3.
The first excursion goes to +1 and back, costing 2. The second goes to -2 and back, costing 4; it does not reach -3. The third goes to +4 and back, costing 8. On the fourth excursion, the searcher encounters the target after moving 3 units left and stops before reaching the planned -8 endpoint.
Total travel is 2+4+8+3=17. The informed searcher would travel 3, giving ratio 17/3, approximately 5.666667. Charging a full return trip after discovery would incorrectly inflate the search cost.
For a separate target at +5, the first four excursions fail, costing 2+4+8+16=30. The fifth reaches the target after 5 additional units, for total 35 and ratio 7. These instances do not achieve the worst-case bound; a competitive ratio is a worst-case guarantee, not the cost of every target.
To see the bound, suppose discovery occurs on excursion k, whose planned reach is 2^k. Completed earlier round trips cost 2 times the sum of 1 through 2^(k-1), or 2(2^k-1). Add the final direct distance d. For k>=2, the previous excursion on the same side reached 2^(k-2), so d>2^(k-2). Therefore total travel is less than 8d+d=9d. The first two excursions satisfy the bound separately under d>=1.
The bound can be approached. Place a right-side target just beyond a large previously explored right endpoint R=4^j. The searcher misses it on that excursion, explores left to 2R, and then finds it on the rightward excursion toward 4R. If its distance is R+epsilon, total travel is 8R-2+R+epsilon. Dividing by R+epsilon approaches 9 as R grows with a fixed small positive epsilon.
The derivation proves the upper bound for this schedule. The stronger statement that no deterministic strategy improves the classic worst-case ratio is a known result cited in the source, not established by these example calculations.

Illustrative case study

In a fictional robotics workshop, Alder Path Labs compares a doubling strategy with several fixed-distance exploration rules in a one-dimensional simulator. It records distance traveled until detection and compares that with the direct distance for each fixed target.
The team then adds turning delays and unreliable detection as separate experiments. It does not assume the original factor-nine analysis still applies unchanged. The case illustrates testing under explicit assumptions.

Common misconceptions and mistakes

Do not call the strategy logarithmic-time simply because the excursion lengths double. The number of direction changes grows logarithmically with target distance, but physical travel remains proportional to distance under the competitive bound. Do not double distances from the current endpoint when the schedule specifies distances from the origin.
The lower distance scale matters for a purely multiplicative bound. If targets can be arbitrarily close on the initially wrong side, a fixed positive first excursion can make the travel-to-distance ratio arbitrarily large. State a lower bound or use an appropriately qualified additive-constant formulation.

Business use

Business relevance is mainly as a disciplined model of exploration under missing information. It helps separate the unavoidable cost of not knowing a target's location from a poorly designed search policy. Before applying it operationally, examine whether travel cost is symmetric, the line is unbounded, detection is reliable, and a target remains stationary. A practical corridor or inspection task may require a different objective and constraints.

Check your understanding

Why does the target at -3 cost 17 rather than 22 units to find?

Answer: The final excursion stops after 3 units when the target is reached. It does not complete the planned trip to -8 or return to the origin.

Related terms

Online algorithm
Search cost
Exploration
Competitive analysis
Cow-path problem
Doubling strategy
Offline optimum
Adversary
Randomized algorithm

Learn next

Calculate the travel cost for targets at +4 and just beyond +4 using the same schedule. Explain the sharp change and compare it with the result for a target at -4. Keep the target distance and completed round trips separate in your accounting.

Sources

Primary teaching source: MIT 6.046 Competitive Analysis recitation, robot search and cow-path discussion: https://people.csail.mit.edu/sukhaj/6.046/rec9.pdf . Target locations, complete cost traces, and upper-bound derivation are original.

Previous: Linear search Next: Linear separability