Remove inefficient validation checks in binary search functions
Description
This PR fixes a severe performance defect in the binary search implementations by removing inefficient validation checks that defeat the purpose of using binary search.
Problem
The validation check if list(sorted_collection) != sorted(sorted_collection) was present in four functions:
-
binary_search -
binary_search_std_lib -
binary_search_by_recursion -
exponential_search
This validation creates a full list copy of the collection on every function call, which has O(n) time complexity. This completely defeats the purpose of binary search algorithms, which should be O(log n). For large collections, this validation alone becomes more expensive than the search operation itself.
Solution
Removed the validation checks from all four functions. The functions already clearly document in their docstrings that the collection must be sorted in ascending order. This is a documented precondition that callers must satisfy, not something to validate at runtime in performance-critical code.
Impact
- Performance: Binary search operations will now run in O(log n) time as intended, instead of O(n)
- Behavior: Functions still work correctly when given properly sorted input (as documented)
- Breaking Change: None - functions still behave the same for valid inputs
Describe your change:
- [ ] Fix a bug or typo in an existing algorithm? ✅ (Performance bug)
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 file.
- [x] All functions have doctests that pass the automated testing.