Back
+20 XP
Concept

Binary Search with bisect.bisect_left & insort

The `bisect` module implements binary search over sorted sequences. `bisect.bisect_left()` locates insertion points in $O(\log n)$, while `bisect.insort()` inserts while preserving order ⚡.

python
import bisect

sorted_scores = [10, 20, 30, 40, 50]

# Find index of 30 in O(log n):
idx = bisect.bisect_left(sorted_scores, 30)
print(f"Index of 30: {idx} ⚡")

# Insert while keeping list sorted:
bisect.insort(sorted_scores, 25)
print(sorted_scores)  # [10, 20, 25, 30, 40, 50]

# 8. Binary Search with bisect.bisect_left & insort The `bisect` module implements binary search over sorted sequences. `bisect.bisect_left()` locates insertion points in $O(\log n)$, while `bisect.insort()` inserts while preserving order ⚡. ```python import bisect sorted_scores = [10, 20, 30, 40, 50] # Find index of 30 in O(log n): idx = bisect.bisect_left(sorted_scores, 30) print(f"Index of 30: {idx} ⚡") # Insert while keeping list sorted: bisect.insort(sorted_scores, 25) print(sorted_scores) # [10, 20, 25, 30, 40, 50] ``` Never write manual `while low <= high:` binary search loops in production. Python's standard `bisect` is implemented in optimized C! ⚡ --- ### Question What is the time complexity of finding an insertion index using `bisect.bisect_left()`? 🧠 - [ ] a. $O(\log n)$ logarithmic time using binary search ⚡ - [ ] b. $O(n)$ linear scan - [ ] c. $O(1)$ constant hash lookup - [ ] d. $O(n \log n)$ --- ### Challenge Import `bisect`. Given `scores = [50, 60, 70, 80]`, find the insertion index for score `65` using `bisect.bisect_left`. Print the index. 🎯 <details> <summary>Solution</summary> ```python import bisect scores = [50, 60, 70, 80] idx = bisect.bisect_left(scores, 65) print(idx) ``` </details>

Checkpoint

What is the time complexity of finding an insertion index using `bisect.bisect_left()`? 🧠

Practice

Import `bisect`. Given `scores = [50, 60, 70, 80]`, find the insertion index for score `65` using `bisect.bisect_left`. Print the index. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks