Array Bisection Algorithm ใน Python (โมดูล bisect)

โมดูล bisect ใช้ Binary Search หาตำแหน่ง Insert ใน Sorted List รักษาลำดับเรียงได้ใน O(log n) + O(n) Insert

import bisect

ฟังก์ชันหลัก

Function	คำอธิบาย	Duplicate Handling
`bisect_left(a, x, lo=0, hi=len(a))`	หาตำแหน่งซ้ายสุดที่ Insert ได้	Insert ก่อน Duplicates
`bisect_right(a, x, lo=0, hi=len(a))`	หาตำแหน่งขวาสุดที่ Insert ได้	Insert หลัง Duplicates
`bisect(a, x, lo=0, hi=len(a))`	Alias ของ bisect_right	Insert หลัง Duplicates
`insort_left(a, x, lo=0, hi=len(a))`	Insert จริง (Left)	Insert ก่อน Duplicates
`insort_right(a, x, lo=0, hi=len(a))`	Insert จริง (Right)	Insert หลัง Duplicates
`insort(a, x, lo=0, hi=len(a))`	Alias ของ insort_right	Insert หลัง Duplicates

โค้ดตัวอย่าง

import bisect

data = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]

# หาตำแหน่ง
print(f"Insert 53: bisect={bisect.bisect(data, 53)}")      # 4
print(f"Insert 69: bisect_left={bisect.bisect_left(data, 69)}")   # 5
print(f"Insert 69: bisect_right={bisect.bisect_right(data, 69)}") # 8

# Insert จริง
bisect.insort(data, 59)
print(f"After insort 59: {data}")
# [11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120]

bisect.insort_left(data, 78)
print(f"After insort_left 78: {data}")
# [11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]

การประยุกต์ใช้: Grade Lookup

import bisect

# Grade Boundaries: <60=F, <70=D, <80=C, <90=B, >=90=A
boundaries = [60, 70, 80, 90]
grades = 'FDCBA'

def get_grade(score):
    i = bisect.bisect(boundaries, score)
    return grades[i]

for s in [55, 65, 72, 85, 95, 100]:
    print(f"Score {s}: Grade {get_grade(s)}")

ผลลัพธ์

Score 55: Grade F
Score 65: Grade D
Score 72: Grade C
Score 85: Grade B
Score 95: Grade A
Score 100: Grade A

การประยุกต์ใช้อื่นๆ

Time-based Lookup: Timestamp Sorted -> หา Event ก่อน/หลังเวลา
Percentile Calculation: bisect ใน Sorted Array
Interval Management: Non-overlapping Intervals
Leaderboard: Insert Score เรียงลำดับ

Complexities

Operation	Time	Space
bisect_left/right	O(log n)	O(1)
insort_left/right	O(n)	O(1)

> **หมายเหตุ:** Insert เป็น O(n) เพราะต้อง Shift Elements ใน List หาก Insert บ่อย ควรใช้ blist, sortedcontainers.SortedList, หรือ Balanced BST

bisect ใน Standard Library อื่นๆ

heapq - Heap Queue (Priority Queue)
array - Typed Arrays (รองรับ bisect)
statistics - ใช้ bisect ภายในสำหรับ Median/Quantiles