Skip to content

bpo-4356: Add key parameter to functions in bisect module #11781

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
remilapeyre wants to merge 13 commits into from
Closed

bpo-4356: Add key parameter to functions in bisect module #11781

Changes from 1 commit
Commits
Show all changes
13 commits
Select commit Hold shift + click to select a range
e36dd1e
Add key parameter to functions in bisect module
Feb 7, 2019
d6082a5
Support None as argument
Feb 7, 2019
b7aaa1a
Fix documentation
Feb 7, 2019
1bc959d
Improve documentation
Mar 17, 2019
adb5a54
Merge remote-tracking branch 'origin/master' into add-key-argument-to…
May 31, 2019
e1ce337
Split logic for key=None
May 31, 2019
4337e73
Test that key is a keyword only argument
May 31, 2019
d9022a9
Make key a keyword only argument
May 31, 2019
84c18be
Add note in the documentation regarding lru_cache
May 31, 2019
54960ed
Add test for reverse support
May 31, 2019
ef98658
Add reverse support
May 31, 2019
49ef1f7
Whitelist suspicious constructs in documentation
May 31, 2019
6bfe7bc
Implement reverse bisect in Python
Jun 8, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Implement reverse bisect in Python
  • Loading branch information
Rémi Lapeyre
Rémi Lapeyre committed Jun 8, 2019
commit 6bfe7bce87531cddfdc83542821555de0bb61b2e
36 changes: 36 additions & 0 deletions Lib/bisect.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -35,6 +35,15 @@ def bisect_right(a, x, lo=0, hi=None, *, key=None, reverse=False):
hi = len(a)

if key is None:
if reverse:
while lo < hi:
mid = (lo+hi)//2
if x > a[mid]:
hi = mid
else:
lo = mid+1
return lo

while lo < hi:
mid = (lo+hi)//2
if x < a[mid]:
Expand All @@ -45,6 +54,15 @@ def bisect_right(a, x, lo=0, hi=None, *, key=None, reverse=False):

x_value = key(x)

if reverse:
while lo < hi:
mid = (lo+hi)//2
if x_value > key(a[mid]):
hi = mid
else:
lo = mid+1
return lo

while lo < hi:
mid = (lo+hi)//2
if x_value < key(a[mid]):
Expand Down Expand Up @@ -89,6 +107,15 @@ def bisect_left(a, x, lo=0, hi=None, *, key=None, reverse=False):
hi = len(a)

if key is None:
if reverse:
while lo < hi:
mid = (lo+hi)//2
if a[mid] > x:
lo = mid+1
else:
hi = mid
return lo

while lo < hi:
mid = (lo+hi)//2
if a[mid] < x:
Expand All @@ -99,6 +126,15 @@ def bisect_left(a, x, lo=0, hi=None, *, key=None, reverse=False):

x_value = key(x)

if reverse:
while lo < hi:
mid = (lo+hi)//2
if key(a[mid]) > x_value:
lo = mid+1
else:
hi = mid
return lo

while lo < hi:
mid = (lo+hi)//2
if key(a[mid]) < x_value:
Expand Down