A binary search extension of Python `bisect` module that enables flexible comparisons.
Project description
more_bisect
A binary search extension of Python bisect
module that enables flexible comparisons.
Includes these functions:
first_pos_eq
: find the first index of value equal tox
last_pos_eq
: find the last index of value equal tox
last_pos_lt
: find the last index of value less thanx
last_pos_le
: find the last index of value less than or equal tox
first_pos_gt
: find the first index of value greater thanx
first_pos_ge
: find the first index of value greater than or equal tox
bisect_left
: the same asbisect.bisect_left
bisect_right
: the same asbisect.bisect_right
last_closest_to
: find the last index of value closest tox
first_closest_to
: find the first index of value closest tox
All functions are of the same signature:
(x, a=None, lo=None, hi=None, key=None)
x
: the value based on which to searcha
: the array to search for; if providedNone
,key
will be used to form an array (see below)lo
,hi
: bound the range (left inclusive, right exclusive) of array to searchkey
: ifa
is notNone
,a[i]
will be mapped tokey(a[i])
on each indexi
; ifa
isNone
,a[i]
will be mapped tokey(i)
on each indexi
. This way, whena
isNone
, not all elements of the fake array need to be given before binary search
Installation
pip install more_bisect
View the package at PyPI.
Examples
- Invoke
first_pos_eq
with an array:
import more_bisect
more_bisect.first_pos_eq(3, [2, 3, 3, 4, 4, 4])
- Invoke
last_closest_to
with a function (the code snippet can be a solution to LeetCode 887 Super Egg Drop:
import more_bisect
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
memo = {}
def recur(k, n):
if (k, n) not in memo:
if n == 0:
ans = 0
elif k == 1:
ans = n
else:
i = more_bisect.last_closest_to(
0, lo=1, hi=n + 1,
key=lambda x: recur(k - 1, x - 1) - recur(k, n - x))
ans = 1 + max(recur(k - 1, i - 1), recur(k, n - i))
memo[k, n] = ans
return memo[k, n]
return recur(k, n)
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
more_bisect-0.1.1.tar.gz
(4.8 kB
view hashes)
Built Distribution
Close
Hashes for more_bisect-0.1.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 91a8364f6c88544504d437ae1e0a7829deb15b004b70b29c1f6711497a56a233 |
|
MD5 | 3836c2ebb1c36d13e8e34a91b58434af |
|
BLAKE2b-256 | 916f2fb7b4fdaf074bbbfab194d4d1cb18762456aa7b3119432eb9fea0cf0bf6 |