Python icon indicating copy to clipboard operation
Python copied to clipboard

Fix binary search to return leftmost occurrence for duplicates

Open CommitToday opened this issue 1 month ago • 0 comments

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:

  1. Modified the iterative binary_search function to continue searching to the left after finding a match to locate the leftmost occurrence
  2. Rewrote the recursive binary_search_by_recursion function with an inner helper function that properly handles finding the leftmost occurrence
  3. Added specific test cases like binary_search([1, 2, 4, 4, 4, 6, 7], 4) which should return 2 (the index of the leftmost occurrence of 4)
  4. Updated docstrings to clearly document that the function returns the leftmost occurrence when duplicates exist

Closes #13887

CommitToday avatar Nov 10 '25 01:11 CommitToday