SoFunction
Updated on 2025-03-03

Detailed explanation of the usage scenario of Python bisect_left function

introduction

In the programming world of Python, data processing and search operations are very common tasks. The bisect_left function is a powerful tool in the bisect module of the Python standard library. It provides an efficient solution for us to find element insertion position in ordered sequences. This function plays an important role in many specific scenarios, whether it is simple list operations or complex algorithm implementations, it is possible to use it. Next, we will discuss the usage scenarios of the bisect_left function in detail.

1. Basic introduction to bisect_left function

  • bisect_leftFunctions are mainly used to find the location of inserted elements in ordered sequences (such as lists). The position it returns is that after inserting the element into the sequence, the element still maintains the leftmost position of the sequence. For example, a list arranged in ascending order[1, 3, 5, 7]If you want to insert an element4，bisect_leftThe function will return2, because4Insert to index as2Location (i.e.5Before), the ascending nature of the list can be maintained.

2. Use scenarios

2.1 Maintaining an ordered list

  • Scene description：
    • Suppose we have an ordered list that stores student grades, and whenever new grades are added, we want to insert them in the right place to keep the list organized.
  • Code Example：
    • First, importbisectModule:
import bisect
  • Then, create an initial score list:
scores = [60, 70, 80, 90]
  • When new achievements75When inserting, usebisect_leftFunction to determine the insertion position:
new_score = 75
insert_index = bisect.bisect_left(scores, new_score)
(insert_index, new_score)
print(scores)
    • The output result is[60, 70, 75, 80, 90], you can see new results75It is correctly inserted into the appropriate position, maintaining the ascending order of the list.
  • Advantages Analysis：
    • Compared to manually traversing the list to find the insertion position,bisect_leftThe time complexity of the function is O ( l o g n ) O(log n) O(logn), which is more efficient when processing large ordered lists. It takes advantage of the ordered characteristics of the sequence and quickly locates the insertion position through binary search, greatly reducing the time cost of the insertion operation.

2.2 Implement custom sorting rules

  • Scene description：
    • Sometimes, we may need to sort elements by rules defined by ourselves. For example, in a string containing date (formatYYYY - MM - DDIn the list of ) we want to sort in the order of dates and also insert in the correct order when inserting new dates.
  • Code Example：
    • Define a function that converts a date string to a date object (assuming it is used heredatetimeModule):
from datetime import datetime
def date_str_to_obj(date_str):
    return (date_str, '%Y - %M - %D')
  • Create a list of date strings:
def compare_dates(date_str1, date_str2):
    date1 = date_str_to_obj(date_str1)
    date2 = date_str_to_obj(date_str2)
    return date1 - date2
  • When there is a new date2024 - 01 - 15When inserting, usebisect_leftFunctions combine comparison functions to determine the insertion position:
new_date_str = '2024 - 01 - 15'
insert_index = bisect.bisect_left(dates_str, new_date_str, key=compare_dates)
dates_str.insert(insert_index, new_date_str)
print(dates_str)
    • The output results will correctly insert the new date in the order of dates, such as['2024 - 01 - 01', '2024 - 01 - 15', '2024 - 02 - 01', '2024 - 03 - 01']。
  • Advantages Analysis：
    • By customizing the comparison function,bisect_leftFunctions can adapt to various complex sorting rules. This flexibility makes it very useful when dealing with data with non-standard sorting requirements, such as customizing the sorting of objects, sorting by multiple conditions, and other scenarios.

2.3 Variants of binary search

  • Scene description：
    • In some algorithmic problems, we may need to find the first element in an ordered sequence that is greater than or equal to the given value. For example, in an ordered temperature record list, look for the first recording time greater than or equal to a given temperature.
  • Code Example：
    • Suppose we have a list of temperature records where each element is a tuple containing temperature and timestamps:
temperature_records = [(20, '08:00'), (22, '09:00'), (25, '10:00'), (28, '11:00')]
  • Define a function to find the first timestamp greater than or equal to the given temperature:
def find_first_greater_or_equal(temperature):
    index = bisect.bisect_left(temperature_records, (temperature,))
    if index < len(temperature_records):
        return temperature_records[index][1]
    else:
        return None
  • For example, find the first one greater than or equal to23Timestamp of degree:
print(find_first_greater_or_equal(23))
    • The output result is09:00, because in the temperature record,22The corresponding timestamp of degree is09:00, this is the first one greater than or equal to23record of degrees (assuming the temperature is arranged in ascending order here).
  • Advantages Analysis：
    • This application is a variant of binary search.bisect_leftFunctions provide a simple and efficient way to implement this search operation. Compared with traditional linear search, its time complexity advantage is obvious, and it can significantly improve the search efficiency and reduce the calculation time when processing large ordered data sets.

2.4 Implement priority queues (similar functions)

  • Scene description：
    • Suppose we are developing a task scheduling system where tasks have different priorities and we want to handle tasks in priority order. Availablebisect_leftFunction to simulate a simple priority queue.
  • Code Example：
    • First, define a task class that contains the task name and priority:
class Task:
    def __init__(self, name, priority):
         = name
         = priority
    def __lt__(self, other):
        return  <
  • Create a task list:
tasks = []
  • When a new task is added, usebisect_leftFunction to determine the insertion position:
task1 = Task("Task 1", 3)
insert_index = bisect.bisect_left(tasks, task1)
(insert_index, task1)
task2 = Task("Task 2", 1)
insert_index = bisect.bisect_left(tasks, task2)
(insert_index, task2)
task3 = Task("Task 3", 2)
insert_index = bisect.bisect_left(tasks, task3)
(insert_index, task3)
  • When processing tasks, you can process them in the order in which tasks are in the list (priority from high to low):
for task in tasks:
    print()
    • The output results will output the task name in order from high to low priority (the smaller the number, the higher the priority), such asTask 2、Task 3、Task 1。
  • Advantages Analysis：
    • Although Python has a dedicated priority queue implementation (e.g.), but in some simple scenarios, usebisect_leftFunctions to build structures similar to priority queues can be more flexible. It allows us to customize task sorting rules according to our needs, and the insertion operation is relatively efficient, which can meet the task scheduling needs of a certain scale.

3. Summary

bisect_leftFunctions are a very practical tool in Python, and their usage scenarios cover multiple aspects such as maintaining ordered lists, implementing custom sorting rules, binary search variant applications, and simulating priority queues. It uses the characteristics of ordered sequences to determine the location of element insertion through an efficient binary search algorithm, providing convenience for us to handle tasks related to various ordered data structures. In actual programming, flexibly use it according to specific application scenariosbisect_leftFunctions can improve the efficiency and readability of the code.

The above is the detailed explanation of the usage scenario of the Python bisect_left function. For more information about the usage of the Python bisect_left function, please pay attention to my other related articles!