PYTHON
Efficiently Manage Sorted Lists with Python `bisect`
Explore Python's `bisect` module to maintain sorted lists efficiently, enabling fast insertion of elements while preserving order and performing quick lookups in ordered data.
import bisect
# A list that needs to stay sorted
scores = [10, 25, 40, 55, 70, 85]
print(f"Initial scores: {scores}")
# Insert a new score while maintaining sorted order
new_score = 60
bisect.insort_left(scores, new_score)
print(f"Scores after inserting {new_score}: {scores}")
new_score_2 = 10
bisect.insort_right(scores, new_score_2)
print(f"Scores after inserting {new_score_2} (right): {scores}")
# Find insertion point (index where element would be inserted)
# bisect_left returns an insertion point which comes before (to the left of) any existing entries of x in a.
index_for_50 = bisect.bisect_left(scores, 50)
print(f"Insertion index for 50 (left): {index_for_50}") # Will insert 50 at this index
scores.insert(index_for_50, 50)
print(f"Scores after inserting 50 manually at calculated index: {scores}")
scores.remove(50) # Removing for next example
# bisect_right returns an insertion point which comes after (to the right of) any existing entries of x in a.
index_for_70 = bisect.bisect_right(scores, 70)
print(f"Insertion index for 70 (right): {index_for_70}")
# Use bisect to quickly find elements within a range (e.g., scores between 20 and 70)
min_val = 20
max_val = 70
low_idx = bisect.bisect_left(scores, min_val)
high_idx = bisect.bisect_right(scores, max_val)
scores_in_range = scores[low_idx:high_idx]
print(f"Scores between {min_val} and {max_val}: {scores_in_range}")
How it works: The `bisect` module provides functions for manipulating lists that are treated as sorted sequences. It's highly efficient for inserting items into a sorted list while keeping it sorted (`insort_left`, `insort_right`) and for finding insertion points (`bisect_left`, `bisect_right`). This is particularly useful in web applications for maintaining sorted data like leaderboards, logs, or event timelines where new entries arrive frequently and must be kept in order for quick access or range queries without the overhead of re-sorting the entire list each time.