جستجوی دودویی (Binary Search) چطور کار می‌کند؟

 

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

یکی از روش های جستجوی سریع در نرم افزار، جستجوی دودویی یا همان (Binary Search) است. در این مقاله از آکادمی برنامه نویسی کدیاد قصد داریم تا این الگوریتم جستجو را از چیستی، نحوه کارکرد تا پیچیدگی زمانی آن را محاسبه کنیم. 

برای درک دقیق و درست این الگوریتم جستجوی سریع، خواندن این مقاله به شما عزیزان بسیار پیشنهاد می شود، پس در ادامه با ما همراه باشید…

 

مفهوم سرچ یا جستجو در نرم افزار

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

علم برنامه نویسی و برنامه نویس این امکان را برای شما با یک زبان برنامه نویسی فراهم میسازد تا بتوانید با مقادیر مشخصی به یک داده مشخص در نرم افزار و پایگاه داده به آسانی  دسترسی پیدا کنید. یکی از روش های جستجو که به جستجوی سریع هم معروف است جستجوی دودویی یا همان (Binary Search) است.

 

جستجوی دودویی چیست؟ 

زمانی وجود دارد که شما می خواهید یک عنصر خاصی را در یک مجموعه داده، لیست، آرایه و یا مجموعه اطلاعات خاصی از پایگاه داده به صورت مرتب شده پیدا کنید و نیاز به یک روش و یا ابزاری دارید تا این کار را برای شما انجام دهد. الگوریتم جستجوی دودویی Binary Search این کار را برای شما انجام خواهد داد. 

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

 

مزایا و معایب جستجوی دودویی

نکته ای که باید در مورد این الگوریتم جستجوی پر سرعت بدانید این است که در کنار داشتن مزایای جذاب و کاربردی برای برنامه نویسان و کاربران یک نرم افزار، معایبی هم به همراه خواهد داشت که سعی کردیم در این قسمت به صورت جذابی آن را برای شما توصیف کنیم. برخی از مزایا و معایب جستجوی دودویی Binary Search عبارت اند از : 

 

 

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

 

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

در قسمت های قبلی این مقاله ما به سرعت بی نظیر و جذاب این الگوریتم بارها و بارها اشاره کردیم و گفتیم یکی از کاربرد های جذاب جستجوی دودویی در میزان داده های بسیار حجیم و بزرگ است که سرعت بسیار بالایی در جستجوی داده ها دارد. این مزیت جستجوی دودویی باعث شده است تا در قسمت های دیگر هم ما بتوانیم از این الگوریتم جستجو استفاده کنیم. برخی از کاربرد های شگفت انگیز جستجوی دودویی در برنامه نویسی عبارت اند از : 

 

• جستجوی سریع در دیتابیس ها
• جستجو در داده های پزشکی به صورت تخصصی
• سیستم های advisor یا توصیه گر
• تحلیل سیستم های مالی و اقتصادی
• مسیریابی شبکه ها
• جستجوی داده در سیستم های امنیتی

و …

 

نحوه کار جستجوی دودویی همراه با مثال

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

حال بیایید تا گام های این جستجوی جذاب را همراه با یک مثال بررسی کنیم. فرض کنید که شما دارای یک لیست داده یا همان آرایه (Array) هستید که در قسمت پایین می توانید آن را مشاهده کنید: 

 

[1.3.5.6.7.8.11.15.20.21]

 

هدف از این مسئله این است که ما اندیس مقدار 5 را بیابیم و در خروجی به کاربر نمایش دهیم. مراحل انجام این الگوریتم به صورت زیر خواهد بود : 

 

1. دریافت ورودی : قبل از جستجو باید داده هایی را در قالب یک آرایه به این جستجو ارائه دهید که می توانید از کاربر و یا به صورت ثابت آن را دریافت کنید. حتما این را در نظر داشته باشید که مقادیر آرایه باید حتما به صورت صعودی مرتب شده باشد و در غیر این صورت شما خطا دریافت خواهید کرد و نتیجه ی اشتباه در خروجی دریافت خواهید کرد.
2. تعیین بازه ی جستجو ی اصلی : بازه ی جستجو یعنی اینکه کوچکترین عنصر این آرایه کدام است که باید در اندیس 0 باشد و همچنین بزرگترین عنصر این آرایه باید در آخرین اندیس آرایه ذخیره شده باشد.
3. محاسبه ی عنصر میانی : برای اینکه بتوانید این آرایه را به 2 قسمت مساوی تقسیم کنید و عملکرد جستجو را شروع کنید باید از فرمول low + high /2 استفاده کنید تا عنصر Mid را بدست آورید.
4. مقایسه ی عنصر Mid با عنصر هدف : در این قسمت باید این را بررسی کنید که آیا عنصر Mid با عنصر هدف برابر است؟ حالت اول این است که اگر Mid با عنصر هدف برابر باشد، خروجی هدف چاپ می شود و تمام می شود ولی حالت دوم این است که اگر عنصر Mid بزرگتر از عنصر مورد نظر باشد، الگوریتم نیمه ی کوچک تر سمت چپ را دوباره به عنوان بازه ی جدید برای تقسیم در نظر میگیرد. در حالت سوم اینگونه است که اگر عنصر Mid از عنصر هدف کوچک تر باشد الگوریتم نیمه ی بزرگ تر سمت راست را دوباره به عنوان بازه ی جدید در نظر میگیرد تا به هدف برسد.
5. تکرار کردن مرحله ی 2 تا 4 : در صورت داشتن حجم عظیمی از داده ها انقدر مرحله ی 2 تا 4 انجام  می شود تا الگوریتم به نتیجه برسد. 
6. نمایش خروجی : در نهایت عنصر هدف در خروجی برای کاربر نمایش داده می شود.

 

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

در این قسمت از مقاله قصد داریم تا نحوه ی پیاده سازی الگوریتم جستجوی دودویی با همان (Binary Search) را در زبان های مختلف برنامه نویسی مقایسه کنیم و این نتیجه را بدست بیاوریم که کدام زبان در پیاده سازی راحت تر عمل می کند. دو زبان برنامه نویسی که در این قسمت در نظر گرفتیم، زبان برنامه نویسی پایتون و زبان برنامه نویسی PHP است. 

 

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

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  # عنصر یافت نشد

# مثال استفاده از تابع
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7

result = binary_search(sorted_list, target)

if result != -1:
    print(f"عنصر {target} در ایندکس {result} پیدا شد")
else:
    print(f"عنصر {target} در لیست وجود ندارد")

 

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

<?php
function binarySearch($arr, $target) {
    $low = 0;
    $high = count($arr) - 1;
    
    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);  // پیدا کردن نقطه وسط
        
        if ($arr[$mid] == $target) {
            return $mid;  // عنصر پیدا شد
        } elseif ($arr[$mid] < $target) {
            $low = $mid + 1;  // جستجو در نیمه راست
        } else {
            $high = $mid - 1;  // جستجو در نیمه چپ
        }
    }
    
    return -1;  // عنصر یافت نشد
}

// مثال استفاده از تابع
$sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
$target = 7;

$result = binarySearch($sortedArray, $target);

if ($result != -1) {
    echo "عنصر $target در ایندکس $result پیدا شد";
} else {
    echo "عنصر $target در آرایه وجود ندارد";
}
?>

 

چند تمرین برای حرفه ای تر شدن در الگوریتم جستجوی دودویی

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

 

1. پیدا کردن نام در دفترچه تلفن

فرض کنید یک دفترچه تلفن به ترتیب حروف الفبا دارید و می‌خواهید نام "زهرا" را پیدا کنید. جستجوی دودویی به شما کمک می‌کند به جای بررسی تک‌تک اسامی، به صورت سیستماتیک نام را پیدا کنید.

 

2. حدس عدد بین 1 تا 100

بازی معروف "حدس عدد": شما عددی بین 1 تا 100 در نظر می‌گیرید و دوستتان باید با کمترین سؤال آن را حدس بزند. استراتژی بهینه استفاده از جستجوی دودویی است (مثلاً اول می‌پرسد: "بالای 50؟").

 

3. یافتن کتاب در کتابخانه

در یک کتابخانه که کتاب‌ها بر اساس شماره دیویی مرتب شده‌اند، چگونه می‌توانید کتابی با شماره خاص را سریع پیدا کنید؟ جستجوی دودویی روش کارآمدی است.

 

4. پیدا کردن تاریخ در تقویم تاریخی

اگر یک جدول مرتب شده از رویدادهای تاریخی بر اساس تاریخ داشته باشید و بخواهید بدانید در 15 خرداد 1342 چه اتفاقی افتاده است، جستجوی دودویی کمک می‌کند.

 

5. تشخیص سریع قبولی در کنکور

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

 

سوالات متداول 

1.جستجوی دودویی در چه نوع داده‌هایی جواب می‌دهد؟

فقط روی داده‌های از قبل مرتب‌شده کار می‌کند. مثلاً لیست اعداد صعودی یا نزولی، اسامی الفبایی و هر ساختار مرتب‌شده دیگر. اگر داده‌ها نامرتب باشند، این روش کارایی ندارد.

 

2.چرا در مثال کتابخانه از جستجوی دودویی استفاده می‌شود؟

چون کتاب‌ها معمولاً براساس شماره یا عنوان مرتب هستند. این روش به جای گشتن تک‌تک قفسه‌ها، مستقیماً بخش موردنظر را پیدا می‌کند، درست مثل وقتی که وسط دفترچه تلفن را نگاه می‌کنید.

 

3.آیا جستجوی دودویی برای لیست‌های کوتاه هم مناسب است؟

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

 

4.این روش در کدام برنامه‌های واقعی استفاده می‌شود؟

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

 

5.اگر داده‌ها مرتب نباشند چطور می‌توان از این روش استفاده کرد؟

یا باید اول داده‌ها را مرتب کنید (که خودش زمان می‌برد)، یا از روش‌های دیگر مثل جستجوی خطی استفاده کنید. البته بعضی زبان‌های برنامه‌نویسی کتابخانه‌هایی دارند که این کارها را خودشان انجام می‌دهند