05. Searching
Searching
1. Basic Concepts
- Searching: Determining whether a given value exists in a data structure and returning its position
- Search table: Static search table, dynamic search table
2. Sequential Search
- Compare one by one, suitable for unsorted tables, time complexity O(n)
3. Block Search
- Divide the table into several blocks, search sequentially within blocks, use an index between blocks, suitable for large tables
4. Binary Search
- Suitable for sorted tables, halve the range each time, time complexity O(log n)
5. B-Tree and B+ Tree
- B-Tree: Multi-way balanced search tree, suitable for disk storage
- B+ Tree: All keys are in leaf nodes, suitable for range search
6. Hash Table
- Hash function, collision handling (open addressing, chaining)
- High search efficiency, close to O(1)
7. String Pattern Matching
- Naive algorithm, KMP algorithm, etc.
8. Analysis and Application of Search Algorithms
- Search efficiency, space complexity, applicable scenarios
Exercises
- Briefly describe the applicable conditions and efficiency of sequential search and binary search.
- What is the basic idea of block search?
- What are the differences between B-Tree and B+ Tree?
- How does a hash table handle collisions?
- What are the commonly used algorithms for string pattern matching?
Reference Answers
1. Sequential Search and Binary Search
Sequential search is suitable for unsorted tables, O(n); binary search is suitable for sorted tables, O(log n)
2. Block Search Idea
Block + index, locate the block first, then search sequentially, suitable for large tables
3. Differences between B-Tree and B+ Tree
B-Tree keys are distributed in all nodes, B+ Tree only in leaf nodes; B+ Tree is suitable for range search
4. Hash Collision Handling
Open addressing, chaining, etc.
5. String Matching Algorithms
Naive algorithm, KMP algorithm, etc.