Search algorithm

A search algorithm looks for an object satisfying a specified condition within a collection or state space. Linear search inspects entries directly; binary search exploits sorted order; breadth-first search explores graph states by distance from a start. The specification should say whether to return one witness, every witness or proof of absence. A procedure that eventually finds every reachable witness may still fail to terminate when none exists in an infinite space. Representation and available structure determine which candidates can safely be ruled out without inspection.

Nearest neighbor search retrieves an element of a stored set minimizing its distance from a query. For a finite set $S$ in a metric space with distance $d$, the exact task is to return $x_{\ast }\in S$ satisfyingFor example, among $(0,0)$, $(3,0)$ and $(0,4)$, the nearest point to $(2,1)$ in Euclidean distance is $(3,0)$, at distance $\sqrt{2}$. Scanning all $n$ points in $d$ dimensions takes $O(nd)$ arithmetic work; a useful index eliminates candidates while preserving the required guarantee.

In a recommender system, stored items and queries can be vectors learned by machine learning. The comparison rule matters: minimizing Euclidean distance and maximizing dot product need not rank items identically. For unit vectors, $\Vert q-x{\Vert }^2=2-2⟨q,x⟩$, so those two rankings coincide.^[ref]

Iterative lengthening search repeatedly runs cost-bounded depth-first search, starting with threshold zero and replacing each unsuccessful threshold by the smallest rejected path cost. It uses a depth-first search stack rather than the potentially large search frontier of uniform-cost search.

Suppose an optimal plan has cost $C^{\ast }$ and each pass terminates. At every unsuccessful threshold $L<C^{\ast }$, some first rejected prefix of an optimal plan has path cost at most $C^{\ast }$. Therefore the next threshold is no larger than $C^{\ast }$. Any first returned goal state has cost at most $C^{\ast }$ and hence exactly $C^{\ast }$. Finite branching factor and a positive lower bound on step costs ensure that only finitely many search nodes precede that cost, giving completeness as well as optimality. With arbitrary real step costs, the threshold increments can be much smaller than the smallest step cost: the difference between two path costs need not itself be a step cost.

Search a matrix whose rows and columns are both nondecreasing by inspecting the top-right corner of the remaining rectangle. If that value is below the target, discard its row; if above, discard its column; if equal, return its coordinates. The loop invariant retains every possible match inside the rectangle. Each failure decreases its remaining height plus width by one, proving at most $n+m-1$ inspections for positive dimensions and constant auxiliary space. Row monotonicity alone is insufficient for the column exclusion.

A search algorithm whose OR nodes represent controllable choices and whose AND nodes require solutions for every possible outcome of a chosen action. In nondeterministic planning, a successful OR choice needs successful continuations for all its AND children. In contingent planning, those children can represent different observations and updated belief states. Cycle handling must match the required solution concept: ignoring a repeated state is not a proof that the goal will inevitably be reached.

Find two distinct input positions whose values sum to a target, or establish that no such pair exists. Distinct values are not required: two equal values may form a pair when they occur at different positions. On a sorted array, distinct-index two-sum by suffix lower bounds gives $O(N\log N)$ running time, while a two-pointer technique can give linear time.

A lower-bound search that probes two positions to retain one of three subintervals. For unresolved $[lo,hi)$ of positive length $d$, put $q=\lfloor d/3\rfloor$, $m_1=lo+q$ and $m_2=hi-1-q$. If $a(m_1)\ge x$, retain $[lo,m_1)$; if $a(m_2)<x$, retain $[m_2+1,hi)$; otherwise retain $[m_1+1,m_2)$. Sortedness preserves the lower-bound partition. The new interval lengths are $q,q,d-2q-2$, and the feasible middle case has nonnegative length at most $q$. This proves strict progress and $O(\log (N+1))$ comparison cost. Equality must retain the first possible boundary rather than return an arbitrary matching occurrence.

A search algorithm is optimal for a specified objective if its returned solution has the best objective value among all solutions. The objective is part of the claim: minimizing the number of actions does not generally maximize a reward assigned to terminal states. Breadth-first tree search optimizes total cost when all actions have the same positive cost.

A search algorithm is complete for a specified class of problems if it finds a solution whenever a solution exists in that class. This definition need not require termination on unsolvable instances; an additional termination guarantee should be stated separately. A finite branching factor makes breadth-first tree search complete for finite-depth solutions, while depth-first tree search additionally needs a reason it cannot be trapped on an infinite branch.

A search algorithm that explores action histories in a search tree. Two histories ending in the same state remain distinct nodes unless an additional repetition rule identifies them. Consequently a finite state space can generate an infinite search tree: a legal stay action at a nonterminal state already suffices. A graph search instead records explored states to control repetitions. Confusing these models changes termination and completeness claims.