This is a beta course, so its structure, chapters, and examples may continue to change.
Searching Algorithms: Analysis & Applications
| Algorithm | Time | Space | Scenario |
|---|---|---|---|
| Sequential | Unordered/small | ||
| Block | Large table, frequent | ||
| Binary | Sorted list | ||
| Hash | (amort.) | Very frequent / big data | |
| B/B+ Tree | Disk/DB index | ||
| String matching | (KMP) | Text/sequence |
Search algorithm efficiency comparison demo
This placeholder can be extended with comparison charts of search algorithm efficiency and space complexity.
- Sequential search: O(n)
- Block search: O(√n)
- Binary search: O(log₂ n)
- Hash table search: O(1)
- B-tree / B+ tree search: O(logₘ n)
- String pattern matching (KMP): O(m+n)
- Sequential/Binary: simple, tiny space
- Hash/B-Tree: extra structures, higher space, more complex
- Small, unordered: sequential
- Large, frequent lookups: hash, B/B+
- Sorted list: binary
- Range queries: B+
- Strings/sequences: KMP, etc.
Exercise 1
Compare sequential, binary, and hash search (time + scenarios).
Approach: Compare the efficiency and the applications.
Steps:
- Sequential , for unordered or small data
- Binary , for sorted lists
- Hash , for large data or frequent lookups
Answer: Sequential search for small tables, binary search for sorted lists, hash search for large data.
Exercise 2
Which structure suits frequent lookups and range queries, and why?
Approach: Range queries plus frequent lookups point to a B+ tree.
Steps:
- For frequent lookups together with range queries, the B+ tree is the best choice
- Its linked leaf list makes range queries easy
Answer: A B+ tree.
2021·408
Analyse hash search versus B-Tree search on big data.
Approach: Equality search versus range search; space versus disk friendliness.
Steps:
- Hash search is fast and good for equality lookups, but it uses more space and is weak at range queries
- The B-tree is a little slower, but disk friendly and it supports range queries
Answer: Hash search is fast but not suitable for range queries; the B-tree suits disk storage and range queries.