Searching algorithms study guide

1. Start by identifying the search structure

Before tracing, identify whether the data is presented as a sequence or as a binary tree. A linear search operates by checking items in order. A binary search operates on a sorted list and repeatedly selects a middle item from the remaining range. A binary tree search begins at the root and moves from node to node through branches. Correctly identifying the structure prevents using the wrong tracing method.

2. Trace linear search precisely

Write the items in their search order. Compare the target with the first item, then the second, and continue until the target is found or the final item has been checked. For [12, 4, 19, 7] and target 19, the comparison sequence is 12, 4, 19. The trace ends at 19; the final item does not need to be checked. If the target were absent, all four items would appear in the trace. The complexity is O(n) because the search progresses through the sequence and the number of possible checks is linked to the number of items.

3. Trace binary search using ranges

For binary search, keep a written record of the current range. Select its middle item, compare it with the target, and discard the part that cannot contain the target. For [3, 6, 9, 12, 15, 18, 21], a search for 18 checks 12 first, then retains the higher section [15, 18, 21], and then checks 18. The important reasoning is not only that the target is found, but that each comparison determines which remaining section is searched next. The time complexity is O(log n) because the search repeatedly reduces the remaining search area.

4. Trace binary tree search as a path

Begin with the root and record each node compared with the target. At every stage, follow the appropriate branch and ignore the other branch for that trace. The result should be a path through the tree, not a list of every node in the tree. For a target found at a later node, explain each decision that led from the root to that node. Binary tree search has time complexity O(log n) according to the specification.

5. Apply complexity reasoning in an exam

When asked to analyse complexity, name the algorithm and give its required complexity: linear search is O(n), while binary search and binary tree search are O(log n). Then connect the notation to the mechanism. Linear search may continue through the sequence item by item. Binary search reduces the remaining list at successive middle-item decisions. Binary tree search follows successive node and branch decisions. Do not replace a complexity answer with only a trace: a trace gives particular comparisons, whereas complexity gives the algorithm's stated growth classification.

6. Self-check checklist

• Can you list every comparison in a linear search and stop at the correct point?
• Can you show the changing range in a binary search?
• Can you identify the middle item used at every binary-search stage?
• Can you record only the visited path in a binary tree search?
• Can you state O(n) for linear search and O(log n) for both binary search and binary tree search?
• Can you explain why the trace and the complexity analysis are different parts of an answer?

A strong answer combines the trace, the decisions made at each step, and the correct complexity notation.