QUESTION 21 · Searching
Linear search can be used directly.
QUESTION 22 · Searching
Linear search examines successive elements. Binary search uses sorted order to discard half of the remaining interval at each step.
It can start immediately on an unsorted array. It compares the key with each element until it finds a match or reaches the end. A first-element match is O(1), while the worst case is O(n). A simple first-match version returns the first occurrence when duplicates exist.
It requires sorted input. It compares the key with a midpoint and retains only the possible half. A midpoint match is O(1), and the worst case is O(log n) for indexed arrays. A basic version does not guarantee the first duplicate. The iterative version needs O(1) auxiliary space.
For a small unsorted list and one search, linear search is simple and avoids a preliminary sort. If an array is already sorted or will support many searches, binary search can reduce work per query. Sorting and later maintaining sorted order have costs of their own.
For five unsorted marks, scanning directly may be the appropriate task. For thousands of already sorted roll numbers, repeatedly halving the interval is useful. The correct choice depends on input order, the number of searches and the representation.
The complexity of the search function differs from the total cost of reading, sorting or validating its input. A binary-search sample that checks every adjacent pair first spends O(n) on that validation, even though the actual search remains O(log n).
| Feature | Linear | Binary |
|---|---|---|
| Input order | Any | Ascending for shown version |
| Best search time | O(1) | O(1) |
| Worst search time | O(n) | O(log n) |
| Auxiliary space | O(1) | O(1) |
| Duplicate result | First in shown version | Any match in shown version |
Related questions in the linear search category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.
Describe linear search with an example and give its time complexity in all cases.
Paper P02 · page 2Write the linear-search algorithm and explain with an example.
Paper P05 · page 2