Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 2c15b8c

Browse files
shuhao-alan-fanpre-commit-ci[bot]Copilotpoyea
authored
[Searches] Fix Binary Search bug with duplicate elements (TheAlgorithms#13946)
* Fix binary search with duplicates issue TheAlgorithms#13886 * Add docstrings to binary search functions Added docstrings for lower_bound and upper_bound functions. * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Update searches/binary_search.py Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com> * Refactor docstrings for lower_bound and upper_bound Updated docstring parameter and return type annotations for lower_bound and upper_bound functions. * Update searches/binary_search.py Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com> --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com> Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com> Co-authored-by: John Law <johnlaw.po@gmail.com>
1 parent 8934bab commit 2c15b8c

File tree

1 file changed

+75
-0
lines changed

1 file changed

+75
-0
lines changed

‎searches/binary_search.py‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -243,6 +243,81 @@ def binary_search_std_lib(sorted_collection: list[int], item: int) -> int:
243243
return -1
244244

245245

246+
def binary_search_with_duplicates(sorted_collection: list[int], item: int) -> list[int]:
247+
"""Pure implementation of a binary search algorithm in Python that supports
248+
duplicates.
249+
250+
Resources used:
251+
https://stackoverflow.com/questions/13197552/using-binary-search-with-sorted-array-with-duplicates
252+
253+
The collection must be sorted in ascending order; otherwise the result will be
254+
unpredictable. If the target appears multiple times, this function returns a
255+
list of all indexes where the target occurs. If the target is not found,
256+
this function returns an empty list.
257+
258+
:param sorted_collection: some ascending sorted collection with comparable items
259+
:param item: item value to search for
260+
:return: a list of indexes where the item is found (empty list if not found)
261+
262+
Examples:
263+
>>> binary_search_with_duplicates([0, 5, 7, 10, 15], 0)
264+
[0]
265+
>>> binary_search_with_duplicates([0, 5, 7, 10, 15], 15)
266+
[4]
267+
>>> binary_search_with_duplicates([1, 2, 2, 2, 3], 2)
268+
[1, 2, 3]
269+
>>> binary_search_with_duplicates([1, 2, 2, 2, 3], 4)
270+
[]
271+
"""
272+
if list(sorted_collection) != sorted(sorted_collection):
273+
raise ValueError("sorted_collection must be sorted in ascending order")
274+
275+
def lower_bound(sorted_collection: list[int], item: int) -> int:
276+
"""
277+
Returns the index of the first element greater than or equal to the item.
278+
279+
:param sorted_collection: The sorted list to search.
280+
:param item: The item to find the lower bound for.
281+
:return: The index where the item can be inserted while maintaining order.
282+
"""
283+
left = 0
284+
right = len(sorted_collection)
285+
while left < right:
286+
midpoint = left + (right - left) // 2
287+
current_item = sorted_collection[midpoint]
288+
if current_item < item:
289+
left = midpoint + 1
290+
else:
291+
right = midpoint
292+
return left
293+
294+
def upper_bound(sorted_collection: list[int], item: int) -> int:
295+
"""
296+
Returns the index of the first element strictly greater than the item.
297+
298+
:param sorted_collection: The sorted list to search.
299+
:param item: The item to find the upper bound for.
300+
:return: The index where the item can be inserted after all existing instances.
301+
"""
302+
left = 0
303+
right = len(sorted_collection)
304+
while left < right:
305+
midpoint = left + (right - left) // 2
306+
current_item = sorted_collection[midpoint]
307+
if current_item <= item:
308+
left = midpoint + 1
309+
else:
310+
right = midpoint
311+
return left
312+
313+
left = lower_bound(sorted_collection, item)
314+
right = upper_bound(sorted_collection, item)
315+
316+
if left == len(sorted_collection) or sorted_collection[left] != item:
317+
return []
318+
return list(range(left, right))
319+
320+
246321
def binary_search_by_recursion(
247322
sorted_collection: list[int], item: int, left: int = 0, right: int = -1
248323
) -> int:

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /