1. Searching in Data Structures
Searching algorithms locate a target element within an explicitly stored, structured collection. Unlike state-space search, the data set is fully materialised: every element already exists in memory and is addressable by index or key.
1.1 Algorithms
| Algorithm | Paradigm | Precondition | Worst-case cost |
|---|---|---|---|
| Linear Search | Brute force | None | \(O(n)\) |
| Binary Search | Divide and conquer | Sorted array | \(O(\log n)\) |
The choice between the two is determined almost entirely by whether the data is sorted and whether the underlying container supports \(O(1)\) random access:
- Linear search is correct for any sequence regardless of order or container type. It is optimal for unsorted data.
- Binary search requires a sorted random-access array but reduces the search cost from linear to logarithmic by halving the candidate interval at every step.
More efficient structures — hash tables, balanced BSTs — achieve \(O(1)\) expected or \(O(\log n)\) worst-case lookup but fall under data structure design rather than search algorithm design and are therefore treated separately.