آموزش جامع ماژول bisect در پایتون (جستجوی دودویی)

ماژول bisect در پایتون ابزاری قدرتمند برای کار با لیست‌های مرتب (Sorted Lists) است. این ماژول از الگوریتم جستجوی دودویی (Binary Search) استفاده می‌کند تا بدون نیاز به مرتب‌سازی مجدد لیست پس از هر بار درج آیتم، لیست را مرتب نگه دارد. این روش از نظر عملکرد بسیار بهینه‌تر از روش‌های معمول جستجوی خطی یا مرتب‌سازی مکرر است.

سطح مقدماتی (Beginner Level)

در این سطح، با مفاهیم پایه‌ی ماژول bisect، نحوه پیدا کردن ایندکس مناسب و درج آیتم‌ها در لیست‌های مرتب آشنا می‌شویم.

۱. مفهوم جستجوی دودویی و پیش‌نیازها

مهم‌ترین نکته در استفاده از bisect این است که لیست ورودی شما باید از قبل مرتب شده باشد. اگر لیست نامرتب باشد، نتایج این ماژول غیرقابل پیش‌بینی و نادرست خواهد بود.

ماژول bisect دو کار اصلی انجام می‌دهد:

1. پیدا کردن مکانی که یک آیتم باید در آن قرار بگیرد تا ترتیب لیست حفظ شود.
2. درج آیتم در مکان مناسب.

۲. پیدا کردن موقعیت با bisect

تابع bisect (که نام مستعار bisect_right است) ایندکسی را برمی‌گرداند که اگر آیتم جدید را در آنجا درج کنیم، لیست همچنان مرتب باقی می‌ماند. اگر آیتم تکراری باشد، موقعیت بعد از آخرین تکرار (سمت راست) را برمی‌گرداند.

مثال اول: پیدا کردن مکان درج ساده

در این مثال، می‌خواهیم عدد 4 را در لیست مرتب [1, 2, 5, 7] قرار دهیم.

مثال دوم: تفاوت bisect_left و bisect_right

زمانی که اعداد تکراری در لیست داریم، تفاوت این دو تابع مشخص می‌شود:

• bisect_left: اولین ایندکس ممکن (سمت چپ تکرارها) را برمی‌گرداند.
• bisect_right: آخرین ایندکس ممکن (سمت راست تکرارها) را برمی‌گرداند.

۳. درج آیتم با insort

به جای اینکه ابتدا ایندکس را پیدا کنید و سپس با متد insert() لیست، آیتم را اضافه کنید، می‌توانید از insort استفاده کنید که هر دو کار را یکجا و بهینه انجام می‌دهد.

مثال سوم: درج خودکار و حفظ ترتیب

مثال چهارم: استفاده از insort_left

اگر بخواهیم آیتم تکراری قبل از آیتم‌های موجود قرار بگیرد:

سطح پیشرفته (Professional Level)

در سطح حرفه‌ای، به بررسی کارایی زمانی (Time Complexity)، استفاده از کلیدهای مرتب‌سازی (Key Functions) در پایتون‌های جدید، و کاربردهای واقعی مانند دسته‌بندی داده‌ها می‌پردازیم.

۱. پیچیدگی زمانی و بهینه‌سازی

استفاده از bisect دارای پیچیدگی زمانی O(log n) برای جستجو است، در حالی که جستجوی خطی (Linear Search) دارای پیچیدگی O(n) است. اما نکته مهم در عمل درج (insort) است: هرچند پیدا کردن مکان درج O(log n) است، اما عملیات درج در لیست پایتون همچنان O(n) هزینه دارد زیرا باید عناصر را شیفت دهد. با این حال، استفاده از insort بسیار سریع‌تر و خواناتر از ترکیب دستی sort() بعد از هر append() است.

قطعه کد استاتیک: مقایسه منطقی

# روش کند و غیرحرفه‌ای برای لیست‌های بزرگ
def slow_add(sorted_list, item):
    sorted_list.append(item)
    sorted_list.sort()  # بسیار پرهزینه: O(n log n)

# روش حرفه‌ای با bisect
import bisect
def fast_add(sorted_list, item):
    bisect.insort(sorted_list, item)  # ترکیب O(log n) و O(n)

۲. نگاشت داده‌های عددی به بازه‌ها (Numeric Lookups)

یکی از کاربردهای رایج bisect در سطح حرفه‌ای، تبدیل نمرات یا اعداد پیوسته به دسته‌بندی‌های گسسته (مثل تبدیل نمره به گرید A, B, C) است. این کار با استفاده از breakpoints انجام می‌شود.

مثال پنجم: سیستم نمره‌دهی

در این مثال از ویژگی بازگشتی ایندکس برای نگاشت نمره به گرید استفاده می‌کنیم.

۳. استفاده از آرگومان key (پایتون ۳.۱۰ به بالا)

در نسخه‌های قدیمی پایتون، bisect فقط روی مقادیر مستقیم لیست کار می‌کرد. در پایتون ۳.۱۰، پارامتر key اضافه شد که اجازه می‌دهد جستجو را بر اساس یک ویژگی خاص از اشیاء انجام دهیم.

مثال ششم: جستجو در لیستی از تاپل‌ها

فرض کنید لیستی از رکوردهای دیتابیس دارید که بر اساس ID مرتب شده‌اند و می‌خواهید جایگاه یک ID جدید را پیدا کنید.

(نکته: در کد بالا متغیر index_to_insert همان position است. برای اجرا نام متغیر را یکسان در نظر بگیرید. در اینجا برای وضوح خروجی، کد زیر اصلاح شده اجرا می‌شود.)

۴. کار با اشیاء سفارشی (Custom Objects)

اگر نتوانید از پایتون ۳.۱۰ استفاده کنید یا منطق پیچیده‌تری داشته باشید، اشیاء شما باید متدهای مقایسه‌ای مثل __lt__ (کوچکتر از) را پیاده‌سازی کنند تا bisect بتواند آن‌ها را مقایسه کند.

مثال هفتم: تعریف کلاس قابل مقایسه (Static)

class Task:
    def __init__(self, priority, name):
        self.priority = priority
        self.name = name

    # تعریف نحوه مقایسه برای bisect
    def __lt__(self, other):
        return self.priority < other.priority

# این کلاس اکنون می‌تواند در یک لیست مرتب‌شده توسط bisect مدیریت شود

مثال هشتم: اسکریپت کامل مدیریت وظایف (Runnble)

۵. جستجو در لیست‌های معکوس (Descending Order)

ماژول bisect به طور پیش‌فرض برای لیست‌های مرتب شده به صورت صعودی (Ascending) طراحی شده است. برای استفاده در لیست‌های نزولی، یک تکنیک حرفه‌ای استفاده از یک کلاس Wrapper یا استفاده از کلید منفی است.

مثال نهم: مدیریت لیست نزولی با کلید منفی