Bisect.bisect: примеры (PYTHON)
bisect.bisect(a: list, x: any, lo: int, hi: int): intФункция bisect.bisect в Python
Функция bisect.bisect() из модуля bisect выполняет поиск позиции для вставки элемента в отсортированный список, чтобы сохранить порядок сортировки. Метод используется для работы с упорядоченными последовательностями и реализует алгоритм двоичного поиска, обеспечивая эффективность O(log n).
Аргументы функции:
a– отсортированный список, в котором происходит поиск позиции (тип list).x– элемент, позицию вставки которого определяют.lo=0– нижняя граница диапазона поиска (индекс). По умолчанию 0.hi=len(a)– верхняя граница диапазона поиска (индекс). По умолчанию длина списка.key=None– ключевая функция, применяемая к элементам списка перед сравнением. Доступна с Python 3.10.
Возвращаемое значение:
Функция возвращает индекс i, при котором все элементы в срезе a[lo:i] меньше или равны x, а все элементы в срезе a[i:hi] больше x. Если x уже присутствует в списке, позиция вставки находится справа от существующих таких элементов. Существует псевдоним bisect.bisect_right() с идентичным поведением.
Примеры использования bisect.bisect
Пример с отсортированным списком целых чисел:
import bisect
numbers = [1, 3, 5, 7, 9]
print(bisect.bisect(numbers, 4))2
Пример с указанием границ поиска:
import bisect
numbers = [10, 20, 30, 40, 50]
print(bisect.bisect(numbers, 25, 1, 4))2
Пример с ключевой функцией (Python 3.10+):
import bisect
data = [{'id': 1}, {'id': 3}, {'id': 5}]
idx = bisect.bisect(data, 3, key=lambda item: item['id'])
print(idx)2
Пример с дублирующимися элементами:
import bisect
items = [1, 2, 2, 2, 3, 4]
print(bisect.bisect(items, 2))4
Похожие функции в Python
bisect.bisect_left(a, x, lo=0, hi=len(a), key=None) – определяет позицию вставки слева от существующих одинаковых элементов. Возвращает индекс, где все элементы слева строго меньше x.
bisect.insort(a, x, lo=0, hi=len(a), key=None) – вставляет элемент x в список a, сохраняя порядок сортировки. Существует вариант bisect.insort_left().
Функция bisect.bisect() предпочтительнее, когда требуется только найти позицию без модификации списка. Для вставки применяют bisect.insort(). При работе с уникальными элементами разница между bisect_left и bisect_right несущественна.
Аналоги функции в других языках
JavaScript:
const arr = [1, 3, 5, 7, 9];
const index = arr.findIndex(el => el > 4);
console.log(index !== -1 ? index : arr.length);2
Java:
import java.util.Arrays;
int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 4);
int insertionPoint = idx < 0 ? -idx - 1 : idx + 1;
System.out.println(insertionPoint);2
PHP:
$numbers = [1, 3, 5, 7, 9];
$index = array_search(4, $numbers);
if ($index === false) {
$index = count(array_filter($numbers, fn($n) => $n < 4));
}
echo $index;2
Golang:
package main
import "fmt"
import "sort"
func main() {
nums := []int{1, 3, 5, 7, 9}
idx := sort.SearchInts(nums, 4)
fmt.Println(idx)
}2
В отличие от Python, многие языки не имеют встроенной функции, возвращающей позицию вставки справа, и требуют дополнительной обработки.
Типичные ошибки при использовании
Передача неотсортированного списка приводит к неопределенному результату:
import bisect
data = [5, 2, 9, 1]
print(bisect.bisect(data, 3))2 # Результат некорректен, так как список не отсортирован
Использование несовместимых типов данных вызывает исключение:
import bisect
items = ['a', 'b', 'c']
print(bisect.bisect(items, 5))TypeError: '<' not supported between instances of 'int' and 'str'
Некорректные границы поиска могут привести к ошибкам:
import bisect
numbers = [1, 2, 3]
print(bisect.bisect(numbers, 5, 10, 20))IndexError: list index out of range
Изменения в последних версиях
В Python 3.10 добавлен параметр key, позволяющий применять ключевую функцию к элементам списка при сравнении. Это расширяет возможности работы со сложными структурами данных. В более ранних версиях такой параметр отсутствовал.
До Python 3.10 для поиска по ключу требовалась предварительная обработка списка или использование дополнительных функций.
Расширенные примеры применения
Использование с пользовательскими объектами и ключевой функцией:
import bisect
from dataclasses import dataclass
@dataclass
class Item:
name: str
price: float
products = [Item('apple', 1.5), Item('banana', 2.3), Item('orange', 3.0)]
# Сортировка по цене
products.sort(key=lambda x: x.price)
# Поиск позиции для товара с ценой 2.0
idx = bisect.bisect(products, 2.0, key=lambda x: x.price)
print(idx)
# Вставка нового товара
new_item = Item('pear', 2.0)
products.insert(idx, new_item)
print([p.name for p in products])2 ['apple', 'pear', 'banana', 'orange']
Применение для определения диапазонов значений:
import bisect
grades = [60, 70, 80, 90]
letters = ['D', 'C', 'B', 'A', 'S']
def grade_to_letter(score):
return letters[bisect.bisect(grades, score)]
print(grade_to_letter(85))
print(grade_to_letter(95))B S
Использование с числовыми массивами NumPy для поиска позиций:
import bisect
import numpy as np
# bisect работает с обычными списками, но может использоваться для индексов NumPy
arr = np.array([1.1, 2.2, 3.3, 4.4])
idx = bisect.bisect(arr.tolist(), 2.5)
print(idx)
# Альтернативно: np.searchsorted
np_idx = np.searchsorted(arr, 2.5, side='right')
print(np_idx)2 2
Поддержание отсортированной последовательности при потоковом добавлении данных:
import bisect
import random
sorted_stream = []
for _ in range(10):
num = random.randint(1, 100)
pos = bisect.bisect(sorted_stream, num)
sorted_stream.insert(pos, num)
print(f'Добавлено {num} на позицию {pos}: {sorted_stream}')Добавлено 67 на позицию 0: [67] Добавлено 37 на позицию 0: [37, 67] Добавлено 93 на позицию 2: [37, 67, 93] ... # Результаты могут различаться из-за случайности