Python
Python copied to clipboard
Fix binary search to return leftmost occurrence for duplicates
Overview This PR fixes issue #13887 by modifying the binary search implementation to return the index of the leftmost occurrence when there are multiple occurrences of the search item in the sorted collection. Previously, the function would return any arbitrary occurrence.
Checklist
- [x] Code changes implemented in both iterative and recursive binary search functions
- [x] Added test cases to verify the new behavior
- [x] Updated docstrings to reflect the new behavior
Proof The changes include:
- Modified the iterative
binary_searchfunction to continue searching to the left after finding a match to locate the leftmost occurrence - Rewrote the recursive
binary_search_by_recursionfunction with an inner helper function that properly handles finding the leftmost occurrence - Added specific test cases like
binary_search([1, 2, 4, 4, 4, 6, 7], 4)which should return2(the index of the leftmost occurrence of4) - Updated docstrings to clearly document that the function returns the leftmost occurrence when duplicates exist
Closes #13887