Bisect for Binary Search

Introduction

Bisect provides binary search algorithms for sorted sequences, O(log n) search complexity.

Basic Binary Search

import bisect

arr = [1, 3, 5, 7, 9]

pos = bisect.bisect_left(arr, 5)
print(pos)  # 2 - index where 5 would go

pos = bisect.bisect_right(arr, 5)
print(pos)  # 3 - index after 5

# insort (insert while maintaining sort)
bisect.insort_left(arr, 4)  # Insert 4 at position 1
print(arr)  # [1, 3, 4, 5, 7, 9]

Bisect Variations

arr = [1, 2, 2, 2, 3, 4, 5]

bisect.bisect_left(arr, 2)   # 1 - first 2
bisect.bisect_right(arr, 2)  # 4 - after last 2
bisect.bisect(arr, 2)        # Same as right

# All in one call
bisect.insort_left(arr, 2)
bisect.insort_right(arr, 2)

Practical Use

import bisect

def grade_score(score, breakpoints=[60, 70, 80, 90], grades="FDCBA"):
    idx = bisect.bisect_right(breakpoints, score)
    return grades[idx]

print(grade_score(85))  # B

Practice Problems

1. Implement sorted list with duplicates
2. Create interval checking with bisect
3. Find insertion position for new element
4. Implement two-sum variant with sorted array
5. Use bisect for frequency table