مقدمه ای بر الگوریتم جستجوی دودویی

در برنامه‌نویسی، الگوریتم جستجوی دودویی یکی از روش‌های کارآمد برای جستجو در مجموعه‌های مرتب‌شده است. این الگوریتم بر اساس تقسیم و حل مسئله عمل می‌کند و به تدریج با کاهش مجموعه جستجویی، به یافتن عنصر مورد نظر می‌رسد. در این مقاله، به بررسی الگوریتم جستجوی دودویی و نحوه پیاده‌سازی آن در زبان برنامه‌نویسی C# می‌پردازیم.

الگوریتم جستجوی دودویی

الگوریتم جستجوی دودویی به شکل زیر عمل می‌کند:

1. ابتدا محدوده جستجویی را تعیین کنید. این محدوده معمولاً ابتدا از ابتدای آرایه (یا ساختار داده مرتب‌شده) و تا انتهای آن است.
2. بررسی کنید که آیا عنصر میانی مورد نظر با عنصر مورد جستجویی برابر است. در صورت برابر بودن، جستجو با موفقیت پایان می‌یابد.
3. اگر عنصر میانی بزرگتر از عنصر مورد جستجویی باشد، جستجو را در نیمه سمت چپ محدوده ادامه دهید.
4. اگر عنصر میانی کوچکتر از عنصر مورد جستجویی باشد، جستجو را در نیمه سمت راست محدوده ادامه دهید.
5. با تکرار مراحل 2 تا 4، به تدریج محدوده جستجویی را کاهش دهید تا به یافتن عنصر مورد نظر برسید یا متوقف شوید.

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

در زبان برنامه‌نویسی C# می‌توانیم الگوریتم جستجوی دودویی را به شکل زیر پیاده‌سازی کنیم:

 private static int BinarySearch(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (array[mid] == target)
            return mid;

        if (array[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1; // عنصر مورد نظر یافت نشد
}
 

توضیحات

در این پیاده‌سازی، از تابع BinarySearch برای انجام جستجوی دودویی استفاده می‌شود. این تابع به عنوان ورودی آرایه مرتب‌شده و عنصر مورد جستجویی را دریافت می‌کند. ابتدا دو اندیس left و right را برابر ابتدا و انتهای آرایه قرار می‌دهیم. سپس با استفاده از یک حلقه تکراری، در هر مرحله محدوده جستجویی را کاهش می‌دهیم تا به یافتن عنصر مورد نظر برسیم یا متوقف شویم. در هر مرحله، عنصر میانی را با استفاده از متغیر mid محاسبه می‌کنیم و با عنصر مورد جستجویی مقایسه می‌کنیم. اگر عنصر میانی برابر با عنصر مورد جستجویی باشد، جستجو با موفقیت پایان می‌یابد و اندیس متناظر با آن عنصر برگردانده می‌شود. در غیر این صورت، با توجه به مقدار عنصر میانی، محدوده جستجویی را به سمت مناسب تغییر می‌دهیم. در پایان، اگر عنصر مورد نظر در آرایه وجود نداشت، مقدار -1 برگردانده می‌شود.

نتیجه گیری

در این مقاله، الگوریتم جستجوی دودویی را معرفی کرده و نحوه پیاده‌سازی آن در زبان برنامه‌نویسی C# را بررسی کردیم. الگوریتم جستجوی دودویی یکی از الگوریتم‌های پرکاربرد و کارآمد در جستجو در مجموعه‌های مرتب‌شده است و به صورت مؤثر در بسیاری از برنامه‌ها و سیستم‌های نرم‌افزاری استفاده می‌شود. در پایان توصیه می کنیم برای یادگیری هر چه بهتر این مطالب از پکیج کامل آموزش الگوریتم ها و ساختمان داده ها در سی شارپ استفاده کنید.