Movatterモバイル変換

[0]ホーム
URL:

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

Commit2c15b8c

Browse files
shuhao-alan-fanpre-commit-ci[bot]Copilotpoyea
authored
[Searches] Fix Binary Search bug with duplicate elements (#13946)
* Fix binary search with duplicates issue#13886* Add docstrings to binary search functionsAdded docstrings for lower_bound and upper_bound functions.* [pre-commit.ci] auto fixes from pre-commit.com hooksfor more information, seehttps://pre-commit.ci* Update searches/binary_search.pyCo-authored-by: Copilot <175728472+Copilot@users.noreply.github.com>* Refactor docstrings for lower_bound and upper_boundUpdated docstring parameter and return type annotations for lower_bound and upper_bound functions.* Update searches/binary_search.pyCo-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 parent8934bab commit2c15b8c

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+
defbinary_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+
iflist(sorted_collection)!=sorted(sorted_collection):
273+
raiseValueError("sorted_collection must be sorted in ascending order")
274+
275+
deflower_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+
whileleft<right:
286+
midpoint=left+ (right-left)//2
287+
current_item=sorted_collection[midpoint]
288+
ifcurrent_item<item:
289+
left=midpoint+1
290+
else:
291+
right=midpoint
292+
returnleft
293+
294+
defupper_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+
whileleft<right:
305+
midpoint=left+ (right-left)//2
306+
current_item=sorted_collection[midpoint]
307+
ifcurrent_item<=item:
308+
left=midpoint+1
309+
else:
310+
right=midpoint
311+
returnleft
312+
313+
left=lower_bound(sorted_collection,item)
314+
right=upper_bound(sorted_collection,item)
315+
316+
ifleft==len(sorted_collection)orsorted_collection[left]!=item:
317+
return []
318+
returnlist(range(left,right))
319+
320+
246321
defbinary_search_by_recursion(
247322
sorted_collection:list[int],item:int,left:int=0,right:int=-1
248323
)->int:

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp