الگوریتم جستجوی دودویی چیست؟ — معرفی مزایا و معایب آن

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

الگوریتم جست‌جوی دودویی چیست؟

الگوریتم جستجوی دودویی «Binary search algorithm» یک الگوریتم جستجوی کارآمد است که از روش تقسیم و تسخیر برای جستجوی یک عنصر در یک آرایه یا لیست مرتب شده استفاده می‌کند. این الگوریتم یکی از محبوب‌ترین الگوریتم‌های جستجو به شمار می‌آید و از الگوریتم‌های جستجوی خطی، کارآیی بیشتری دارد.

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

پیچیدگی زمانی الگوریتم جستجوی دودویی در زمان لگاریتمی است، یعنی O(logn)، که در آن n تعداد عناصر در آرایه است. این الگوریتم سریع‌تر از الگوریتم جستجوی خطی عمل می‌کند، زیرا در این روش نیازی به پیمایش کل آرایه نیست.

شرایط استفاده از الگوریتم جستجوی دودویی در یک ساختار داده

برای استفاده از الگوریتم جستجوی دودویی، شرایط زیر باید رعایت شود:

1. ساختار داده باید مرتب شده باشد.
2. دسترسی به هر عنصر از ساختار داده باید در زمان ثابت انجام شود.

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

• یادگیری ماشین: الگوریتم جستجوی دودویی به‌عنوان یک پایه برای الگوریتم‌های پیچیده‌تر در یادگیری ماشین، مانند آموزش شبکه‌های عصبی و یافتن هایپرپارامترهای بهینه برای مدل‌ها، استفاده می‌شود.

• گرافیک کامپیوتری: این الگوریتم در الگوریتم‌های گرافیک کامپیوتری مانند ردیابی پرتو (Ray Tracing) یا نگاشت بافت (Texture Mapping) برای جستجو و یافتن داده‌ها کاربرد دارد.
• جستجو در پایگاه‌های داده: جستجوی دودویی می‌تواند در پایگاه داده‌ها برای یافتن سریع رکوردها و اطلاعات استفاده شود، به‌ویژه زمانی که داده‌ها به طور مرتب ذخیره شده‌اند.
• کتابخانه‌ها و فهرست‌ها: در سیستم‌های مدیریت کتابخانه یا فهرست‌های بزرگ، جستجوی دودویی برای پیدا کردن سریع کتاب‌ها یا آیتم‌ها بسیار مفید است.
• الگوریتم‌های جستجوی پیچیده: این الگوریتم به‌عنوان یک جزء اصلی در برخی الگوریتم‌های جستجوی پیچیده‌تر، مانند جستجوی درون‌یابی (Interpolation Search) و جستجوی نمایی (Exponential Search)، به کار می‌رود.
• برنامه‌نویسی و ساخت داده‌ها: در ساختارهای داده‌ای مانند درخت‌های جستجوی دودویی (Binary Search Trees)، الگوریتم جستجوی دودویی برای یافتن، درج و حذف گره‌ها استفاده می‌شود.
• تجزیه و تحلیل داده‌ها: در تجزیه و تحلیل داده‌ها و الگوریتم‌های مرتبط با داده‌های بزرگ، جستجوی دودویی می‌تواند به بهینه‌سازی جستجوها و کاوش‌های اطلاعاتی کمک کند.

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

• سرعت بالا: جستجوی دودویی بسیار سریع‌تر از جستجوی خطی است، به‌ویژه زمانی که با آرایه‌های بزرگ کار می‌کنید. این الگوریتم زمان جستجو را به طور قابل توجهی کاهش می‌دهد.
• کارایی بالا: نسبت به سایر الگوریتم‌های جستجو با زمان پیچیدگی مشابه (مانند جستجوی درون‌یابی و جستجوی نمایی) کارآمدتر است و زمان جستجو به طور کلی به O(logn) می‌رسد.
• معماری مناسب برای داده‌های ذخیره شده: برای جستجو در داده‌های بزرگ که در حافظه‌های خارجی مانند هارد دیسک یا فضای ابری ذخیره شده‌اند، الگوریتم جستجوی دودویی بسیار مناسب است.
• سادگی پیاده‌سازی: پیاده‌سازی الگوریتم جستجوی دودویی نسبتاً ساده و سرراست است، و مفاهیم آن به راحتی قابل درک هستند.

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

• نیاز به مرتب‌سازی: برای استفاده از جستجوی دودویی، آرایه یا مجموعه داده باید از قبل مرتب شده باشد. اگر داده‌ها مرتب نباشند، این الگوریتم کارایی نخواهد داشت.
• نیاز به حافظه متوالی: الگوریتم جستجوی دودویی نیاز دارد که ساختار داده‌ای که در حال جستجواست، در مکان‌های حافظه متوالی ذخیره شده باشد. این موضوع باعث می‌شود که در بعضی از ساختارهای داده، نتوان از این الگوریتم استفاده کرد.
• قابلیت مقایسه: المان‌های آرایه باید قابل مقایسه باشند، به این معنی که باید بتوان آن‌ها را مرتب کرد. این امر ممکن است در برخی موارد مشکل‌ساز باشد، به‌خصوص اگر داده‌ها با ویژگی‌های متفاوت یا ناشناخته باشند.
• عملکرد در داده‌های بسیار پراکنده: در مواردی که داده‌ها بسیار پراکنده یا غالباً تغییر می‌کنند، مرتب‌سازی مداوم می‌تواند باعث کاهش کارایی شود و در نتیجه، زمان صرف شده برای جستجو افزایش یابد.

پیچیدگی زمانی و پیچیدگی فضایی الگوریتم جستجوی دودویی

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

پیچیدگی زمانی الگوریتم جستجوی دودویی

• بهترین حالت: O(1) بهترین پیچیدگی زمانی زمانی رخ می‌دهد که عنصر هدف ما در اولین تکرار پیدا شود، یعنی همان اولین عنصر میانی.
• حالت میانگین: O(logN) پیچیدگی زمانی میانگین الگوریتم جستجوی دودویی O(logN) است.
• بدترین حالت: O(logN) بدترین پیچیدگی زمانی زمانی اتفاق می‌افتد که عنصر هدف ما آخرین عنصر باشد. در این صورت، ما ادامه می‌دهیم به تقسیم کردن تا زمانی که آخرین عنصر باقی بماند که همان عنصر هدف است.

پیچیدگی فضایی الگوریتم جستجوی دودویی

پیچیدگی فضایی الگوریتم جستجوی دودویی O(1) است. این الگوریتم به فضای ثابتی نیاز دارد و نیازی به فضای اضافی ندارد.

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

الگوریتم جستجوی دودویی یک الگوریتم جستجو است که بر اساس اصل تقسیم و تسخیر عمل می‌کند. این الگوریتم عنصر هدف را در یک آرایه مرتب شده جستجو می‌کند.

فرض کنید آرایه مرتب شده‌ای به شکل رو به رو داریم: arr[] = { 2, 6, 11, 16, 22, 34, 39 }.

حالا می‌خواهیم برای عنصر X = 2 جستجو کنیم. ما از الگوریتم جستجوی دودویی برای پیدا کردن اندیس این عنصر در آرایه استفاده می‌کنیم.

گام ۱: ابتدا باید مقدار میانه (mid) آرایه را با استفاده از فرمول زیر محاسبه کنیم:

mid = (low+high)/2

گام ۲: در ابتدا، مقدار low را برابر ۰ و high را برابر اندازه آرایه منهای ۱ (size – ۱) قرار می‌دهیم.

گام ۳: حالا بیایید مقدار میانه را محاسبه کنیم. بنابراین، عنصر در اندیس ۳، مقدار میانه خواهد بود:

mid = (0+6)/2 = 3

در ادامه، ما از مقدار میانه برای جستجوی عنصر هدف استفاده می‌کنیم و مرحله به مرحله جستجوی خود را ادامه می‌دهیم.

گام ۴: حالا بررسی می‌کنیم که آیا عنصر هدف بزرگ‌تر یا کوچک‌تر از arr[mid] است. در اینجا، عنصر هدف ما کوچک‌تر از arr[mid] است، یعنی ۲<16 بنابراین، اکنون باید مقدار high را بهmid−۱ تغییر دهیم.

​high=mid−۱

اکنون، آرایه ما به حالت زیر کاهش می‌یابد:
حالا مقدار میانه (mid) را دوباره محاسبه می‌کنیم:

mid= (0+2)/2=1

حالا دوباره بررسی می‌کنیم که آیا عنصر هدف بزرگ‌تر یا کوچک‌تر از arr[mid] است، یعنی ۲<6 بنابراین، دوباره حجم آرایه‌مان را کاهش می‌دهیم و مقدار high را بهmid−۱ تغییر می‌دهیم.

حالا، هر دو مقدار low و high به یک اندیس اشاره می‌کنند. حالا مقدار میانه (mid) را محاسبه می‌کنیم. مشاهده می‌کنیم که arr[mid]==X یعنی ۲==۲ اکنون، ما اندیس این عنصر را بازمی‌گردانیم.

اگر عنصر مورد نظر در آرایه وجود نداشته باشد، مقدار low و high از روی هم عبور می‌کنند. در این صورت، مقدار -۱ را برمی‌گردانیم.

تفاوت‌های بین الگوریتم جستجوی خطی و الگوریتم جستجوی دودویی

دو الگوریتم جستجوی محبوب عبارتند از جستجوی خطی و جستجوی دودویی. در ادامه، برخی از تفاوت‌های اصلی آن‌ها را بررسی می‌کنیم:

• روش جستجو: الگوریتم جستجوی خطی با بررسی تک‌تک عناصر لیست به دنبال عنصر هدف می‌گردد، در حالی که الگوریتم جستجوی دودویی یک الگوریتم کارآمد برای یافتن یک آیتم در یک لیست مرتب‌شده است.
• نیاز به مرتب‌سازی: جستجوی خطی نیازی به مرتب بودن لیست ندارد، اما جستجوی دودویی مستلزم آن است که عناصر به صورت مرتب باشند.
• پیچیدگی زمانی: پیچیدگی زمانی الگوریتم جستجوی خطی O(N) است که در آن N تعداد عناصر موجود در آرایه است. در مقابل، پیچیدگی زمانی الگوریتم جستجوی دودویی O(logN) است.
• استراتژی: جستجوی خطی به سادگی کار می‌کند ولی برای مجموعه‌های داده بزرگ کارآمد نیست. از سوی دیگر، جستجوی دودویی برای داده‌های بزرگ مناسب و کارآمد است.

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

در سی شارپ، الگوریتم جستجوی دودویی را می‌توان به دو روش تکراری و بازگشتی پیاده‌سازی کرد. در اینجا هر دو روش به همراه توضیحاتی ارائه می‌دهیم:

• روش تکراری (Iterative): این روش از یک حلقه while استفاده می‌کند تا به طور مداوم بازه جستجو را نصف کند. این روش معمولاً در اکثر موارد ترجیح داده می‌شود زیرا سربار فراخوانی‌های بازگشتی را ندارد.

public static int BinarySearchIterative(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2; // جلوگیری از سرریز عدد صحیح

        if (arr[mid] == target)
        {
            return mid; // هدف یافت شد
        }
        else if (arr[mid] < target)
        {
            left = mid + 1; // جستجو در نیمه راست
        }
        else
        {
            right = mid - 1; // جستجو در نیمه چپ
        }
    }

    return -1; // هدف یافت نشد
}

• روش بازگشتی (Recursive): این روش از بازگشت (recursion) استفاده می‌کند تا بازه جستجو را به طور مکرر نصف کند. اگرچه این روش از نظر خوانایی ممکن است جذاب‌تر باشد، اما در آرایه‌های بسیار بزرگ می‌تواند منجر به سربار فراخوانی‌های بازگشتی و در نتیجه کاهش کارایی شود.

public static int BinarySearchRecursive(int[] arr, int target, int left, int right)
{
    if (left > right)
    {
        return -1; // هدف یافت نشد
    }

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

    if (arr[mid] == target)
    {
        return mid; // هدف یافت شد
    }
    else if (arr[mid] < target)
    {
        return BinarySearchRecursive(arr, target, mid + 1, right); // جستجو در نیمه راست
    }
    else
    {
        return BinarySearchRecursive(arr, target, left, mid - 1); // جستجو در نیمه چپ
    }
}

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

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

#include <iostream>  
using namespace std;  
int binarySearch(int a[], int low, int high, int X)   
{    
    int mid;    
    if(high >= low)     
    {  
        mid = (low+ high)/2;
    
/* if the target value is present in the mid */ 
        if(a[mid] == X)    
        {                 
            return mid+1;    
        }    
   /* if the item to be searched is smaller than middle, then it can only be in the left subarray */  
        else if(a[mid] < X)     
        {  
            return binarySearch(a, mid+1, high, X);    
        }    
 /* if the item to be searched is greater than middle, then it can only be in the right subarray */      
    else     
        {  
            return binarySearch(a, low, mid-1, X);    
        }         
    }    
    return -1;     
}

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

در زیر کد جاوا را برای پیاده‌سازی الگوریتم جستجوی دودویی بررسی می‌کنیم.

class BinarySearch { 
    static int binarySearch(int a[], int low, int high, int X)   
    {    
        int mid;    
        if(high>= low)     
        {  
            mid = (low+ high)/2;    
            if(a[mid] == X)    
            {    
                return mid+1; 
 /* if the item to be searched is present in the middle  

           */  

    }    
/* if the item to be searched is smaller than the middle, then it can only  

be in the left subarray */  
            else if (a[mid] < X)     
            {  
                return binarySearch(a, mid+1, end, val);    
            }  
  
 /* if the item to be searched is greater than middle, then it can only be  

in right subarray */  
            else    
            {  
                return binarySearch(a, low, mid-1, X);    
            }    
        }    
        return -1;    
    }

پیاده سازی الگوریتم جستجوی دودویی با پایتون

در این قسمت از مقاله الگوریتم جستجوی دودویی به پیاده سازی الگوریتم جستجوی دودویی با پایتون می‌پردازیم.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# مثال استفاده:
arr = [2, 5, 7, 8, 11, 12]
target = 11
index = binary_search(arr, target)
print(f"Index of {target}: {index}")

این تابع، یک جستجوی دودویی تکراری (iterative) را پیاده سازی می کند. اگر عنصر پیدا شود، اندیس آن را برمی‌گرداند و در غیر این صورت ۱- را برمی‌گرداند. آرایه ورودی باید مرتب شده باشد.

نتیجه گیری

الگوریتم جستجوی دودویی یک روش کارآمد برای پیدا کردن عنصر مورد نظر در یک آرایه مرتب شده است. این الگوریتم با تقسیم آرایه به دو نیمه و مقایسه عنصر میانه با عنصر هدف، تعداد مقایسه‌ها را به حداقل می‌رساند و زمان جستجو را به O(log n) کاهش می‌دهد. این ویژگی باعث می‌شود که جستجوی دودویی یکی از سریع‌ترین روش‌ها برای جستجو در داده‌های بزرگ باشد.

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