Python
Python copied to clipboard
Add Exponential Search algorithm to searches module
PR Checklist:
- [x] I have read
CONTRIBUTING.md - [x] This pull request is all my own work -- I have not plagiarized
- [x] I know that pull requests will not be merged if they fail the automated tests
- [x] This PR only changes one algorithm per file and keeps them modular
- [x] All new Python files are placed inside existing logical directories
- [x] All filenames are lowercase with no spaces or dashes
- [x] All functions and variable names follow Python naming conventions
- [x] All function parameters and return values use Python type hints
- [x] All functions include doctests and pass automated testing
- [x] All new algorithms include at least one usage example or explanation
Note: This PR includes three distinct algorithm contributions, each in their own file with full documentation and formatting.
Author: Michael Alexander Montoya (@cureprotocols)
1. Exponential Search
- Searches efficiently in sorted arrays where the target is closer to the beginning
- Includes a binary search fallback
- Time complexity: O(log i)
- Located in
searches/exponential_search.py
2. Reservoir Sampling
- Samples
krandom items from a data stream or large dataset without knowing its size in advance - Time complexity: O(n)
- Space complexity: O(k)
- Includes doctest and usage block
- Located in
searches/reservoir_sampling.py
3. Union-Find (Disjoint Set with Path Compression)
- Efficient data structure to manage disjoint sets
- Supports path compression and union by rank
- Includes doctests and usage block
- Located in
data_structures/disjoint_set/union_find.py
Each implementation includes:
- Type hints
- Descriptive variable names
- Doctests where applicable
- Follows pre-commit formatting
Author: Michael Alexander Montoya (@cureprotocols)