1. Introduction to Searching
- Searching = Process of finding the location of a specific element in a data structure.
- Essential for data retrieval, processing, and algorithm efficiency.
- Key Concepts:
- Search key – The element we want to find.
- Search space – The dataset where the search is performed.
- Efficiency – Measured by time complexity and number of comparisons.
- Search key – The element we want to find.
2. Types of Searching Techniques
1. Sequential (Linear) Search
- Scan elements one by one from start to end.
- Time Complexity: O(n).
- Advantages: Simple, works on unsorted data.
- Disadvantages: Inefficient for large datasets.
2. Binary Search
- Works on sorted arrays only.
- Divide the array, compare middle element with key, reduce search space by half each time.
- Time Complexity: O(log n).
- Advantages: Fast for large sorted data.
- Disadvantages: Requires sorted data, not suitable for linked lists.
3. Tree Search
- Search in binary search trees (BST).
- Compare key with root, recursively move to left/right subtree.
- Time Complexity: O(h), where h = height of tree.
4. Hashing
- Direct access using hash function.
- Hash Table: Stores key-value pairs.
- Hash Function: Converts key → index in table.
- Collision Resolution Techniques:
- Chaining – Linked list at each index.
- Open Addressing – Linear probing, quadratic probing, double hashing.
- Chaining – Linked list at each index.
- Advantages: Fast access (O(1) on average).
- Disadvantages: Collisions, extra memory for chains.
3. Efficiency Comparisons
| Search Method | Best Case | Average Case | Worst Case | Notes |
| Sequential | O(1) | O(n/2) | O(n) | Works on unsorted data |
| Binary | O(1) | O(log n) | O(log n) | Sorted array required |
| BST | O(1) | O(log n) | O(n) | Depends on tree balance |
| Hashing | O(1) | O(1) | O(n) | Fastest, collisions possible |
4. Key Concepts
- Search Key = Element to find.
- Collision = Two keys mapped to same index in hash table.
- Load Factor = Number of elements / Table size; affects hash efficiency.
- Balanced BST → Ensures O(log n) search.
5. Applications of Searching
- Database Queries – Locate records quickly.
- Dictionary Lookup – Spell check, auto-suggestions.
- Symbol Table in Compiler – Retrieve variable/function info.
- Network Routing – Fast packet lookup.
- Memory Management – Allocate/deallocate blocks efficiently.
✅ Key Takeaways – Unit 9
- Searching = locating specific data efficiently.
- Linear search → simple, unsorted data.
- Binary search → fast, sorted data.
- Tree search → hierarchical structure, efficiency depends on balance.
- Hashing → fastest average access, requires handling collisions.
- Choosing search technique depends on data size, structure, and sorting.
