Metadata-Version: 2.1
Name: jbisect
Version: 0.3.0
Summary: A python package for binary search
Home-page: https://github.com/jesnie/jbisect
License: MIT
Author: Jesper Nielsen
Author-email: jespernielsen1982+jbisect@gmail.com
Requires-Python: >=3.12,<4
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Classifier: Typing :: Typed
Provides-Extra: numpy
Requires-Dist: numpy (>=1.25,<3) ; extra == "numpy"
Project-URL: Repository, https://github.com/jesnie/jbisect
Description-Content-Type: text/markdown

# jbisect

Reusable implementation of the bisect / binary search algorithm.

This (obviously) competes with the standard library
[`bisect`](https://docs.python.org/3.12/library/bisect.html#module-bisect) package. Whereas `bisect`
only searches lists this package supports searching on a function, and supports both integer and
floating-point indices.

## Install with:

```bash
pip install jbisect
```

## Basic searching

`jbisect` provides the function `bisect_seq` for searching sequences:

```python
from jbisect import bisect_seq

print(bisect_seq("011222355", "2"))
```

By default the entire sequence is searched, but you can use the parameters `low` and `high` to limit
the search range:

```python
print(bisect_seq("011222355", "2", low=1, high=5))
```

You can use the `side` parameters to configure whether to return the first match, or just past the
last match:

```python
print(bisect_seq("011222355", "2", side="right"))
```

If you have a sequence that is descending, instead of ascending, you need to set the `ordering`
parameter:

```python
print(bisect_seq("553222110", "2", ordering="descending"))
```

## Searching functions:

The functions `bisect_int_fn` and `bisect_float_fn` can be used to search a function instead of a
sequence. These functions take the same `low`, `high`, `side` and `ordering` arguments as
`bisect_seq`.

```python
from jbisect import bisect_int_fn, bisect_float_fn

print(bisect_int_fn(lambda i: i * i, 16))
print(bisect_float_fn(lambda i: i * i, 2.0))
```

## Searching predicates:

Finally the functions `bisect_int_pred` and `bisect_float_pred` can be used to find the first value
accepted by a predicate. `pred` must be a function that returns a `bool`, and for which there exists
some `x` so that for all `y<x` `pred(y)` is `False`; and for all `y>=x` `pred(y)` is
`True`. `bisect_*_pred` will then find `x`.

```python
from jbisect import bisect_int_pred, bisect_float_pred

print(bisect_int_pred(lambda i: i * i >= 16))
print(bisect_float_pred(lambda i: i * i >= 2.0))
```

## NumPy support:

The package `jbisect.numpy` adds functionality for searching NumPy arrays and functions.
Again, this obviously competes with the NumPy function
[`searchsorted`](https://numpy.org/doc/stable/reference/generated/numpy.searchsorted.html).
However, `searchsorted` is limited in that it only searches existing arrays, and not functions.

`jbisect.numpy` provides three functions `bisect_numpy_array`, `bisect_numpy_fn` and
`bisect_numpy_pred`, mirroring the pure-python functions above. In the case of NumPy, we do not need
to distinguish between `int` and `float` up-front, as this is determined by the `dtype`.

`bisect_numpy_array` takes the new argument `axis` that determines which axis of the input array to
search.

`bisect_numpy_fn` and `bisect_numpy_pred` takes the new arguments `dtype` and `shape` which
determines the dtype and shape of the input to the function/predicate, and the return type of the
function.

```python
import numpy as np

from jbisect.numpy import bisect_numpy_array, bisect_numpy_fn, bisect_numpy_pred

print(bisect_numpy_array([0, 1, 1, 2, 2, 2, 3, 5, 5], 2))

print(
    bisect_numpy_array(
        [
            [
                [111, 112, 113, 114],
                [121, 122, 123, 124],
                [131, 132, 133, 134],
            ],
            [
                [211, 212, 213, 214],
                [221, 222, 223, 224],
                [231, 232, 233, 234],
            ],
        ],
        [[122], [223]],
        axis=1,
    )
)

print(bisect_numpy_fn(lambda i: i * i, 16, low=0, high=1000, shape=(), dtype=np.int64))

print(bisect_numpy_pred(lambda i: i >= 4, shape=[], dtype=np.int64))
```
