AI Hints
Home›DSA in Python Tutorial›Binary Search
DSA in Python · Lesson 47 of 132

The bisect Module

Python's binary search.

⏱ 2 min read▶ Video at 54:38🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Writing binary search by hand is famously easy to get slightly wrong. Python's bisect module has it ready made, tested, and fast. It also answers a more useful question. Where would this value go?

The bisect Module
From the video: The bisect Module
  • Easy to get slightly wrong
  • bisect is ready made
  • Where would it go?

Where does it belong?

Bisect left returns the position where a value would be inserted, to keep the list sorted. If the value is already there, it's the position of the first copy. Bisect right puts it after any copies. And insort inserts the value, in the right place, for you. Run it.

bisect_demo.pypython
import bisect

scores = [10, 20, 20, 30, 50]
print(bisect.bisect_left(scores, 20))
print(bisect.bisect_right(scores, 20))
print(bisect.bisect_left(scores, 35))

bisect.insort(scores, 35)
print(scores)
Output
1
3
4
[10, 20, 20, 30, 35, 50]

Grades with bisect

Here's a neat use. Turn exam marks into grades. The breakpoints are sixty, seventy, eighty, and ninety. Bisect finds which band each mark falls in, and that position picks the grade letter. Run it. No long chain of if statements needed.

grades.pypython
import bisect

def grade(mark, breaks=[60, 70, 80, 90], letters="FDCBA"):
    return letters[bisect.bisect(breaks, mark)]

print([grade(m) for m in [33, 65, 70, 89, 97]])
Output
['F', 'D', 'C', 'B', 'A']

Summary

Bisect left and bisect right find where a value belongs, and insort keeps a list sorted as you add. Next, binary search on answers, a clever twist.

Key takeaways
  • bisect_left
  • bisect_right
  • insort
Next up: Binary Search on Answers — searching for a number