Python icon indicating copy to clipboard operation
Python copied to clipboard

Add Exponential Search algorithm to searches module

Open cureprotocols opened this issue 9 months ago • 0 comments

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 k random 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)

cureprotocols avatar Mar 29 '25 23:03 cureprotocols