Tìm kiếm nhị phân trong Python với module bisect

Module bisect cung cấp thuật toán tìm kiếm nhị phân (binary search) cho list đã sắp xếp. Hiệu quả O(log n) thay vì O(n) của linear search.

Các hàm chính

• bisect_left(a, x, lo=0, hi=len(a)): Vị trí chèn x để giữ thứ tự (bên trái nếu trùng)
• bisect_right(a, x, lo=0, hi=len(a)): Vị trí chèn x (bên phải nếu trùng)
• insort_left/insort_right: Chèn x vào list giữ thứ tự

1. Tìm lần xuất hiện đầu tiên (First occurrence)

from bisect import bisect_left

def find_first(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
print(find_first(a, 4))   # 2
print(find_first(a, 36))  # 7
print(find_first(a, 10))  # -1

2. Tìm giá trị lớn nhất < x (Predecessor)

def find_predecessor(a, x):
    i = bisect_left(a, x)
    if i > 0:
        return i - 1
    return -1

print(find_predecessor(a, 8))   # 4 (giá trị 5)
print(find_predecessor(a, 2))   # -1 (không có giá trị nhỏ hơn 2)

3. Tìm lần xuất hiện cuối cùng (Last occurrence)

from bisect import bisect_right

def find_last(a, x):
    i = bisect_right(a, x)
    if i > 0 and a[i-1] == x:
        return i - 1
    return -1

print(find_last(a, 36))   # 9
print(find_last(a, 4))    # 3
print(find_last(a, 100))  # -1

4. Ứng dụng thực tế: Rating system

# Xếp hạng dựa trên điểm số
thresholds = [50, 60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A', 'A+']

def get_grade(score):
    idx = bisect_right(thresholds, score)
    return grades[idx]

print([get_grade(s) for s in [45, 55, 75, 95]])  # ['F', 'D', 'B', 'A+']

Lưu ý quan trọng

• List phải đã sắp xếp (sorted) trước khi dùng bisect
• bisect dùng cho list, không dùng cho dict/set
• Với list lớn, bisect nhanh hơn linearsearch hàng nghìn lần