Searching Algorithms
Learn about different searching algorithms and their applications in various scenarios.
Linear Search
Basic Linear Search
- Time Complexity: O(n)
- Space Complexity: O(1)
- Best for: Unsorted arrays or small datasets
- Implementation: Simple iteration through elements
Optimized Linear Search
- Sentinel Linear Search: Reduces comparisons by adding a sentinel
- Two-pointer approach: Search from both ends simultaneously
Binary Search Variations
Standard Binary Search
- Time Complexity: O(log n)
- Space Complexity: O(1) iterative, O(log n) recursive
- Prerequisites: Sorted array
- Best for: Finding exact matches in sorted data
Binary Search Variations
- First occurrence: Find the first index of a target value
- Last occurrence: Find the last index of a target value
- Insert position: Find where to insert a value to maintain order
- Range search: Find all occurrences of a target value
Advanced Search Algorithms
Ternary Search
- Time Complexity: O(log₃ n)
- Space Complexity: O(1)
- Best for: Finding maximum/minimum in unimodal functions
- Concept: Divides search space into three parts
Exponential Search
- Time Complexity: O(log n)
- Space Complexity: O(1)
- Best for: Searching in unbounded/infinite arrays
- Concept: Finds range first, then binary search within range
Interpolation Search
- Time Complexity: O(log log n) average, O(n) worst case
- Space Complexity: O(1)
- Best for: Uniformly distributed sorted data
- Concept: Uses interpolation formula to guess position
Search in Special Data Structures
Search in 2D Matrix
- Row-wise sorted matrix: Binary search on each row
- Column-wise sorted matrix: Binary search on each column
- Fully sorted matrix: Modified binary search
Search in Rotated Array
- Find pivot: Identify the rotation point
- Modified binary search: Account for rotation
- Find minimum: Locate the smallest element
Implementation Patterns
Recursive vs Iterative
- Recursive: Cleaner code, uses call stack
- Iterative: More efficient, constant space
Boundary Conditions
- Left boundary: Include or exclude left endpoint
- Right boundary: Include or exclude right endpoint
- Overflow prevention: Use
left + (right - left) / 2
Common Mistakes
- Integer overflow: Use
mid = left + (right - left) / 2 - Infinite loops: Ensure boundaries are updated
- Off-by-one errors: Be careful with boundary conditions
- Wrong comparison: Use appropriate comparison operators
Performance Comparison
| Algorithm | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|
| Linear Search | O(n) | O(1) | Unsorted data |
| Binary Search | O(log n) | O(1) | Sorted data |
| Ternary Search | O(log₃ n) | O(1) | Unimodal functions |
| Exponential Search | O(log n) | O(1) | Unbounded arrays |
| Interpolation Search | O(log log n) | O(1) | Uniform distribution |