โมดูล bisect ใช้ Bisection Algorithm (Binary Search) หาตำแหน่ง insert ใน sorted list ให้เรียงลำดับคงที่ O(log n) แทน O(n) ของ linear search
Functions
| Function | คำอธิบาย |
|---|---|
bisect_left(a, x, lo=0, hi=len(a)) | หาตำแหน่งซ้ายสุดที่ insert x ได้ (ก่อน duplicate) |
bisect_right(a, x, lo=0, hi=len(a)) | หาตำแหน่งขวาสุดที่ insert x ได้ (หลัง duplicate) |
bisect.insort_left(a, x, lo=0, hi=len(a)) | insert x ที่ตำแหน่ง bisect_left |
bisect.insort_right(a, x, lo=0, hi=len(a)) | insert x ที่ตำแหน่ง bisect_right |
bisect.insort(a, x, ...) | alias ของ insort_right |
ตัวอย่าง
>> nums = [45, 21, 34, 87, 56, 12, 5, 98, 30, 63]
>>> nums.sort()
>>> nums
[5, 12, 21, 30, 34, 45, 56, 63, 87, 98]
>>> import bisect
>>> p = bisect.bisect_left(nums, 50)
>>> p
6
>>> nums.insert(p, 50)
>>> nums
[5, 12, 21, 30, 34, 45, 50, 56, 63, 87, 98]
>>> bisect.insort(nums, 29)
>>> nums
[5, 12, 21, 29, 30, 34, 45, 50, 56, 63, 87, 98]การทำงานของ bisect_left vs bisect_right
>> a = [1, 2, 2, 2, 3]
>>> bisect.bisect_left(a, 2)
1
>>> bisect.bisect_right(a, 2)
4
# insort_left → insert ก่อน 2 ทั้งหมด
# insort_right → insert หลัง 2 ทั้งหมดUse Cases
- รักษา Sorted List ขณะ insert แบบ Real-time
- หา Index สำหรับ Insert/Delete ใน O(log n)
- Implement Priority Queue (แทน heapq บางกรณี)
- Lookup ranges:
bisect_left(a, x)ถึงbisect_right(a, y)= elements in [x, y]
ตัวอย่าง: Grade Lookup
>> breakpoints = [60, 70, 80, 90]
>>> grades = 'FDCBA'
>>> def grade(score):
... i = bisect.bisect_right(breakpoints, score)
... return grades[i]
>>> [grade(s) for s in [55, 65, 75, 85, 95]]
['F', 'D', 'C', 'B', 'A']Performance
- Search: O(log n)
- Insert: O(n) (ต้อง shift elements) - แต่หาตำแหน่ง O(log n)
- เหมาะกับ list ขนาดกลาง (ไม่เกินหลายหมื่น) ที่ insert ไม่บ่อยมาก
- ถ้า insert บ่อยมาก ใช้
blistหรือsortedcontainers(external)
