Searching algorithms revision notes

Linear search

A linear search examines items in sequence, starting at the beginning and continuing until the target is found or there are no more items to examine. For example, searching for 14 in [8, 3, 14, 6] checks 8, then 3, then 14. The target is found after three comparisons. If the target is not present, every item is examined before the search finishes.

The time complexity of linear search is O(n), where n represents the number of items being searched. As the number of items increases, the amount of possible checking increases in proportion to n. When tracing, record the current item at each step and stop at the point where the target is found or the data has been exhausted.

Binary search

Binary search works by repeatedly reducing the part of the list that still needs to be searched. In a sorted list, compare the target with the middle item. If the target is smaller, continue with the lower part; if it is larger, continue with the upper part. Repeat this process on the remaining part of the list.

For example, in [2, 5, 8, 11, 14, 17, 20], searching for 17 first checks the middle value 11. Since 17 is larger, the next search is in [14, 17, 20]. The middle value of this remaining section is 17, so the target is found. Binary search has time complexity O(log n). During a trace, show the current search range and the item selected from that range after every reduction.

Binary tree search

A binary tree search starts at the root of a binary tree. At each node, compare the target with the node's value, then continue through the appropriate branch. The trace should identify the node visited at each stage and the branch selected next. The search ends when the target is found or when there is no suitable node left to visit.

The time complexity of binary tree search is O(log n). For a trace, write the sequence of visited nodes in order. Do not list nodes from branches that the search does not visit.

Important distinctions

• Linear search moves through items sequentially and has complexity O(n).
• Binary search repeatedly reduces the remaining list and has complexity O(log n).
• Binary tree search follows nodes and branches and has complexity O(log n).
• A trace describes the actual comparisons and decisions for the given data; a complexity analysis describes how the algorithm scales in terms of n.

Common errors

• Claiming that binary search checks every item in order.
• Giving the final target without showing the comparisons or ranges visited.
• Using O(log n) for linear search.
• Treating a binary tree trace as if all nodes are visited sequentially.
• Failing to stop a trace when the target is found.