Search and Traversal

The Central Idea

A search or traversal algorithm needs a rule for deciding what to examine next.

The collection might be a list, a sorted array, a tree, a graph, or a set of possible states. In every case, the algorithm maintains some notion of what has already been examined and what remains to be explored.

The central question is:

How can we inspect a structured collection systematically without missing relevant possibilities or doing unnecessary work?

Search and Traversal Are Related but Different

A search usually has a target.

For example, given

we might ask whether \(23\) appears in the list.

A traversal is a systematic visit through a structure, often without a single target.

For example, we might visit every vertex in a connected graph in order to record all reachable locations.

What Makes an Algorithm Systematic?

A useful search or traversal procedure specifies:

• where the process begins;
• which items are eligible to be examined next;
• how the next item is selected;
• how previously examined items are recognized;
• when the procedure stops;
• what result is returned.

These rules turn informal exploration into an algorithm.

Search Space

The search space is the collection of possible places in which the desired target or solution might occur.

In a list, the search space consists of positions in the list.

In a graph, it may consist of vertices or edges.

In a puzzle or planning problem, it may consist of reachable states.

The structure of the search space determines which algorithms are appropriate.

Linear Search

The simplest general search method is linear search.

Starting at one end of a list, inspect entries one at a time until either:

• the target is found; or
• the list ends.

Consider

Searching for \(23\) examines

The target is found at the third position.

Linear Search Procedure

1. Begin with the first entry.
2. Compare the current entry with the target.
3. If they match, report success.
4. If they do not match, move to the next entry.
5. If no entries remain, report that the target was not found.

Linear search works even when the entries are not sorted.

Why Linear Search Works

Suppose the target occurs somewhere in a finite list.

Linear search examines the entries in order. Therefore, if the target is present, the algorithm eventually reaches its position.

If the target is absent, every position is eventually checked and the algorithm can correctly report failure.

This reasoning establishes both completeness and termination for a finite list.

Best and Worst Cases for Linear Search

If the target is the first entry, linear search makes only one comparison.

If the target is the final entry, or is not present at all, a list of \(n\) entries may require

comparisons.

Thus the amount of work can grow directly with the size of the list.

Sorted Data Can Change the Strategy

Extra structure can make searching more efficient.

Consider the sorted list

Because the entries are ordered, comparing the target with a middle entry can eliminate an entire portion of the remaining search space.

This is the idea behind binary search.

Binary Search

Binary search applies to an ordered collection in which the middle position can be accessed efficiently.

To search for \(31\) in

first inspect the middle entry:

Since

every entry to the left of \(18\) can be eliminated.

Continuing a Binary Search

The remaining candidates are

Their middle entry is

The target is found after only two comparisons.

Instead of moving one position at a time, binary search repeatedly reduces the remaining search interval.

The Binary Search Invariant

During binary search, a key invariant is:

If the target is present, then it remains inside the current search interval.

Each comparison preserves this property by removing only a region that cannot contain the target.

This invariant is the core reason binary search is correct.

Repeated Halving

If the remaining search interval contains \(n\) entries, one binary-search step reduces the number of candidates to approximately

After two steps, approximately

remain, and after \(k\) steps approximately

remain.

Why Logarithms Appear in Binary Search

Binary search stops once the candidate region has been reduced to roughly one entry.

We therefore ask when

This is equivalent to

Therefore, the number of halving steps grows on the order of

This is much slower growth than \(n\).

Binary Search Requires an Appropriate Structure

Binary search is powerful, but it is not a universal replacement for linear search.

It depends on two important conditions:

• the data must be ordered by the comparison being used;
• the algorithm must be able to access middle positions efficiently.

If these conditions are not available, another method may be more suitable.

From Lists to Networks

Lists have a simple next position.

Graphs and networks are more complicated because a vertex may have several neighbors.

A graph traversal must therefore decide which discovered vertex should be explored next.

Two fundamental strategies are:

• breadth-first search;
• depth-first search.

Graph Traversal Needs a Visited Record

Graphs may contain cycles.

Suppose vertices \(A\), \(B\), and \(C\) satisfy

Without remembering which vertices have already been visited, a traversal could continue around the cycle indefinitely.

Therefore, graph traversals normally maintain a visited set.

Breadth-First Search

Breadth-first search, or BFS, explores a graph in layers.

Starting from a vertex:

1. visit the starting vertex;
2. discover its unvisited neighbors;
3. then explore the neighbors of those vertices;
4. continue outward level by level.

BFS prioritizes vertices that were discovered earliest.

The Queue Behind Breadth-First Search

BFS is naturally implemented with a queue.

A queue follows the principle

first in, first out.

Vertices discovered first are explored first.

This ordering produces the layer-by-layer behavior of breadth-first search.

Example of Breadth-First Search

Suppose the graph has edges

Starting at \(A\), and examining neighbors alphabetically, BFS visits:

Vertices \(B\) and \(C\) are one edge from \(A\), while \(D\), \(E\), and \(F\) are two edges from \(A\).

Breadth-First Search and Shortest Unweighted Paths

In an unweighted graph, BFS discovers vertices in order of increasing distance from the starting vertex.

If a vertex is first discovered at level \(d\), then there is a path of length \(d\) from the start to that vertex.

No shorter path can exist, because every vertex at levels \(0,1,\ldots,d-1\) was already processed first.

This makes BFS a fundamental shortest-path method for unweighted graphs.

Depth-First Search

Depth-first search, or DFS, follows one branch as far as possible before returning to try another branch.

Starting from a vertex:

1. visit the current vertex;
2. choose an unvisited neighbor;
3. continue from that neighbor;
4. when no unvisited neighbor remains, backtrack.

DFS prioritizes depth rather than distance from the starting point.

The Stack Behind Depth-First Search

DFS is naturally associated with a stack.

A stack follows the principle

last in, first out.

The most recently entered unfinished branch is the first one resumed.

Recursive implementations of DFS use the program's call stack to create this behavior automatically.

Example of Depth-First Search

Use the same graph:

Starting at \(A\), and always choosing the alphabetically first unvisited neighbor, one DFS order is

A different neighbor-ordering rule can produce a different valid DFS traversal.

Traversal Order Is Not Always Unique

In many graphs, several neighbors may be available at the same time.

If the algorithm does not specify a tie-breaking rule, different valid traversal orders may result.

For reproducible output, an implementation may impose a rule such as:

• alphabetical order;
• numerical order;
• input order;
• a fixed priority rule.

The traversal strategy and the tie-breaking rule are separate decisions.

BFS and DFS Produce Different Exploration Patterns

Breadth-first search expands outward from the start.

Depth-first search penetrates deeply along one branch.

Their behavior can be summarized as:

• BFS: explore nearby vertices first;
• DFS: explore the current branch first.

Neither strategy is universally better. The appropriate choice depends on the problem.

When Breadth-First Search Is Natural

BFS is especially useful when the problem emphasizes:

• fewest edges from a starting vertex;
• layer or level structure;
• all vertices within a given distance;
• minimum-step solutions in an unweighted state space.

The layer structure is the defining feature.

When Depth-First Search Is Natural

DFS is especially useful when the problem emphasizes:

• exploring entire branches;
• recursive structure;
• backtracking from dead ends;
• detecting structural relationships in graphs;
• systematically exploring a state space.

Later lessons will build on DFS in backtracking and graph algorithms.

Traversing Trees

Trees are graphs with no cycles, so their hierarchical structure makes traversal especially clear.

A rooted tree can be explored:

• level by level, using a breadth-first pattern;
• branch by branch, using a depth-first pattern.

More specialized tree traversals, such as preorder, inorder, and postorder, refine the depth-first idea by specifying when a node is processed relative to its children.

Search Trees and State Spaces

Some problems do not begin with an explicit graph.

Instead, each possible state becomes a vertex, and each legal move becomes an edge.

The resulting structure is a state-space graph or a search tree.

This viewpoint allows traversal algorithms to solve problems involving puzzles, routing, scheduling, games, and planning.

Frontier and Explored Region

It is useful to divide a search into three conceptual regions:

• unseen: not yet discovered;
• frontier: discovered but not yet fully explored;
• explored: already processed.

BFS and DFS differ mainly in how they select the next item from the frontier.

Early Stopping

A traversal does not always need to visit the entire structure.

If the task is to find one target, the algorithm may stop as soon as the target is discovered or processed, depending on the algorithm's design.

Early stopping can save substantial work when the target is encountered quickly.

Complete Traversal

Other tasks require visiting every reachable item.

Examples include:

• counting reachable vertices;
• recording an entire connected component;
• checking whether every required state can be reached;
• building a traversal tree;
• collecting information from all nodes.

In these cases, stopping at the first interesting vertex would be incomplete.

Disconnected Graphs

Starting BFS or DFS from one vertex visits only the vertices reachable from that start.

If a graph is disconnected, some vertices may remain unvisited.

To traverse the entire graph, repeat the traversal from an unvisited vertex until every vertex has been visited.

This procedure naturally separates the graph into connected components.

Visited Does Not Mean Fully Processed

In many implementations, a vertex is marked as visited when it is discovered, not after all of its neighbors have been explored.

Marking early prevents the same vertex from being inserted into the frontier repeatedly.

This small implementation detail is important for both correctness and efficiency.

Traversal Trees

During BFS or DFS, record the edge through which each new vertex was first discovered.

These discovery edges form a tree rooted at the starting vertex.

The tree records one route from the start to every discovered vertex.

In BFS, these routes are shortest in number of edges for an unweighted graph.

Parents and Paths

Suppose vertex \(v\) was first discovered from vertex \(u\).

We may record

Repeatedly following parent links reconstructs a path back to the starting vertex.

Parent records are therefore useful when a search must return not only whether a target exists, but also how to reach it.

Search Success and Search Failure

A search algorithm should define both outcomes precisely.

If the target is found, the algorithm may return:

• a Boolean value such as true;
• the target's position;
• the target vertex;
• a path to the target;
• associated data.

If the target is absent, the algorithm must also return a well-defined failure result.

Correctness Has Two Parts

A search procedure should satisfy:

1. soundness: if it reports success, the target really satisfies the required condition;
2. completeness: if an eligible target exists, the procedure will not miss it.

For finite structures, termination is also essential.

Later lessons will treat algorithm correctness more systematically.

Termination in Finite Traversals

Suppose a finite graph has \(V\) vertices.

If each vertex is marked when first discovered and no visited vertex is placed into the frontier again, then at most

distinct vertices can enter the traversal.

Therefore, the traversal cannot continue forever.

Basic Efficiency of Graph Traversal

Let a graph have

vertices and

edges.

With a standard adjacency-list representation, BFS and DFS can process the reachable portion of the graph in time proportional to

Intuitively, each vertex is discovered a bounded number of times and each edge is examined a bounded number of times.

Representation Matters

The same abstract graph can be represented in different ways.

Common representations include:

• adjacency lists;
• adjacency matrices;
• edge lists.

The representation affects how efficiently neighbors can be found and therefore affects the practical cost of traversal.

Search Strategy and Data Structure Work Together

The strategy determines how the frontier should behave.

The data structure implements that behavior.

• BFS naturally uses a queue.
• DFS naturally uses a stack or recursion.
• Binary search uses interval boundaries on ordered data.
• Linear search advances sequentially through a collection.

Algorithm design often involves matching an abstract strategy to a suitable data structure.

Search Is Often a Decision Process

Some searches answer a yes-or-no question:

• Does the value occur?
• Is the destination reachable?
• Does a valid state exist?
• Is there a path satisfying the conditions?

Other searches must construct an object, such as the path, location, or solution itself.

Distinguishing decision from construction helps clarify what the algorithm must return.

Common Error: Using Binary Search on Unsorted Data

Suppose the list is

Comparing the target with the middle entry does not justify discarding the left or right half, because the list is not ordered.

Binary search is correct only when the ordering condition supports the elimination step.

Common Error: Forgetting to Mark Visited Vertices

In a graph containing a cycle, failing to record visited vertices may cause the same locations to be processed repeatedly.

For example,

can produce an endless loop if the algorithm keeps treating each return to \(A\) as a new discovery.

A visited record prevents this.

Common Error: Confusing BFS with DFS

BFS does not simply mean "visit many vertices."

Its defining property is that earlier-discovered frontier vertices are explored first.

DFS does not simply mean "move to a neighbor."

Its defining property is that the most recently chosen unfinished branch is continued first.

Common Error: Assuming Traversal Order Is Unique

If a vertex has several unvisited neighbors, different tie-breaking rules may create different valid BFS or DFS orders.

Therefore, when an exercise asks for a specific order, use the stated neighbor-ordering convention.

Common Error: Stopping Before the Goal Is Established

Finding one route does not prove that it is shortest unless the search strategy provides that guarantee.

For example, a DFS may find a path to a target quickly, but the path need not use the fewest edges.

BFS provides the shortest-path guarantee in an unweighted graph because of its level-by-level exploration.

A Reliable Procedure for Linear Search

1. Start at the first available position.
2. Compare the current entry with the target.
3. If the target matches, return the requested success information.
4. Otherwise advance to the next position.
5. If no positions remain, return failure.

A Reliable Procedure for Binary Search

1. Verify that the collection is ordered appropriately.
2. Identify the current search interval.
3. Inspect a middle entry.
4. If it matches the target, return success.
5. If the target is smaller, keep the lower portion.
6. If the target is larger, keep the upper portion.
7. Repeat until the target is found or the interval becomes empty.

A Reliable Procedure for Breadth-First Search

1. Choose a starting vertex.
2. Mark it visited.
3. Place it in a queue.
4. Remove the vertex at the front of the queue.
5. Inspect its neighbors.
6. For each unvisited neighbor, mark it visited and place it at the back of the queue.
7. Repeat until the queue is empty or the stopping condition is met.

A Reliable Procedure for Depth-First Search

1. Choose a starting vertex.
2. Mark it visited.
3. Move to an unvisited neighbor if one exists.
4. Continue deeper while possible.
5. When no unvisited neighbor remains, backtrack.
6. Repeat until the frontier is empty or the stopping condition is met.

Example: Choosing a Search Method

Suppose you must determine whether the number \(57\) occurs in an unsorted list.

Linear search is immediately applicable.

If the same data were already sorted and stored in a structure supporting efficient middle access, binary search could reduce the number of comparisons substantially.

The correct algorithm depends on the structure already available.

Example: Reachability in a Network

Suppose a transportation network is represented as a graph and we want to know whether station \(T\) can be reached from station \(S\).

Start BFS or DFS at \(S\).

If \(T\) is discovered, then \(T\) is reachable from \(S\).

If the traversal finishes without discovering \(T\), then no path from \(S\) to \(T\) exists in the represented network.

Example: Finding a Minimum-Edge Route

Suppose every edge in a network represents one transfer and each transfer counts equally.

BFS from the starting vertex explores:

• all vertices one transfer away;
• then all vertices two transfers away;
• then all vertices three transfers away;
• and so on.

Therefore, the first BFS path to the destination uses the minimum possible number of edges.

Example: Exploring a Maze

A maze can be represented as a graph:

• positions become vertices;
• legal moves become edges.

BFS can find a minimum-step route when every move has equal cost.

DFS can explore one corridor deeply, backtrack at dead ends, and eventually cover all reachable positions.

Practice 1: Linear Search

Use linear search to find \(16\) in

List the entries examined in order.

Practice 2: Unsuccessful Linear Search

Search for \(25\) in

How many comparisons are required before failure can be reported?

Practice 3: Binary Search

Use binary search to locate \(42\) in

Record the entries compared with the target.

Practice 4: Search Preconditions

Explain why binary search cannot be applied directly to

using the usual discard-half rule.

Practice 5: BFS Order

A graph has edges

Starting at \(A\), perform BFS using alphabetical order among available neighbors.

Practice 6: DFS Order

Use the same graph:

Starting at \(A\), perform DFS using alphabetical order among unvisited neighbors.

Practice 7: BFS Distance

In the graph

what is the minimum number of edges from \(A\) to \(F\)?

Practice 8: Why a Visited Set Is Needed

Consider the cycle

Explain what can go wrong if a traversal never records previously visited vertices.

Practice 9: Choosing BFS or DFS

You want a path with the fewest edges from a start vertex to a destination in an unweighted graph.

Which fundamental traversal should you prefer, and why?

Practice 10: Entire Disconnected Graph

A graph contains two connected components.

Explain how to modify a single-start BFS or DFS procedure so that every vertex in the entire graph is eventually visited.

Practice Answers

Practice 1

Linear search examines

The target is found on the fourth comparison.

Practice 2

Because \(25\) is absent, every entry must be checked:

Practice 3

The middle entry of the nine-item list is \(31\).

Since \(42>31\), search the upper portion

Using the lower of the two middle positions for this even-sized interval, the next comparison is \(58\). Since \(42<58\), the remaining candidate is \(42\).

One valid comparison sequence is therefore

Practice 4

The list is not sorted. A comparison with a middle entry therefore does not justify discarding either half, because smaller and larger values may occur on both sides.

Practice 5

BFS visits by levels:

Practice 6

Using alphabetical neighbor order, one DFS traversal is

Practice 7

A shortest path is

Therefore, the minimum number of edges is

Practice 8

The traversal can repeatedly move around the cycle and process the same vertices again. A visited set ensures that each vertex is treated as a new discovery only once.

Practice 9

Prefer

BFS explores vertices in increasing number of edges from the start, so the first discovered route to the target has minimum edge count in an unweighted graph.

Practice 10

Start a traversal at any vertex. When that traversal finishes, choose an unvisited vertex and start another traversal. Repeat until no unvisited vertices remain.

What to Remember

• Search attempts to locate a target; traversal systematically visits a structure.
• Linear search works on general finite lists but may inspect every entry.
• Binary search uses ordering to eliminate roughly half of the remaining candidates at each step.
• BFS explores a graph level by level and naturally uses a queue.
• DFS explores one branch deeply and naturally uses a stack or recursion.
• Graph traversals must record visited vertices when cycles are possible.
• BFS finds minimum-edge paths in unweighted graphs.
• The chosen data representation affects the practical cost of searching and traversal.

The most important habit is to identify the structure of the search space before choosing the search strategy.

Where We Go Next

Search and traversal determine how a computational process explores possibilities. Another fundamental task is to rearrange objects into a useful order.

The next lesson, Sorting and Ordering, develops systematic methods for arranging data, comparing sorting strategies, and understanding how order supports later algorithms.