برنامه نویسی 901 بازدید

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

مقدمه

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

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

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

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

جستجوی خطی

کار خود را با توضیح شیوه پیاده‌سازی جستجوی خطی در جاوا اسکریپت آغاز می‌کنیم. یک تابع به نام linearSearch ایجاد می‌کنیم که مقداری را می‌پذیرد که یک عدد صحیح با رشته است و یک آرایه نیز به عنوان پارامتر می‌گیرد. این تابع همه عناصر موجود در آرایه را برای یافتن مقدار مورد نظر می‌گردد و پس از یافتن، موقعیت آن را باز می‌گرداند. اگر مقدار مورد جستجو در آرایه نباشد، مقدار 1- بازگشت می‌یابد. برای مثال فراخوانی این تابع با مقادیر ([ linearSearch(1, [3, 4, 2, 1, 5 باعث بازگشت مقدار 3 می‌شود و فراخوانی آن با مقادیر ([linearSearch(0, [3, 4, 2, 1, 5 مقدار 1- باز می‌گرداند. شبه کد این تابع به صورت زیر است:

پیاده‌سازی جستجوی خطی در جاوا اسکریپت

کد زیر مربوط به پیاده‌سازی الگوریتم جستجوی خطی در جاوا اسکریپت است:

لازم است اشاره کنیم که الگوریتم جستجوی خطی نیازی به استفاده از لیست مرتب شده ندارد. ضمناً این الگوریتم می‌تواند برای استفاده در سناریوهای خاصی مانند جستجوی یک آرایه از اشیا بر اساس کلیدهایشان، سفارشی‌سازی شود. اگر آرایه‌ای از داده‌های مشتریان داشته باشید که شامل کلیدهایی برای نام و نام خانوادگی آن‌ها باشد، می‌توانید بررسی کنید که آیا در آرایه یک مشتری با نام مورد نظر وجود دارد یا نه. در این صورت به جای بررسی این که [list[index با مقدار مورد جستجو برابر است یا نه می‌توانید list[index].first را بررسی کنید.

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

جستجوی دودویی

تصور کنید در یک بازی حدس اعداد شرکت کرده‌اید. از شما خواسته می‌شود که عددی بین 1 تا 100 را حدس بزنید و اگر عدد شما بالاتر یا پایین‌تر از عدد مورد نظر باشد، این موضوع به شما اعلام خواهد شد.

در این حالت راهبرد شما چه می‌تواند باشد؟ آیا باید اعداد به صورت تصادفی انتخاب شوند؟ آیا باید از 1 و سپس 2 و همین طور تا آخر آغاز کنیم تا این که عدد مورد نظر را حدس بزنیم؟ حتی اگر تعداد حدس‌های ما نامحدود باشد، همچنان می‌خواهیم که تعداد حدس‌هایمان کمترین تعداد ممکن باشد. بنابراین باید از حدس عدد 50 شروع کنیم. اگر عدد مورد نظر بالاتر باشد، حدس دوم ما می‌تواند 75 باشد، اگر در مرحله دوم اعلام شود، عدد مورد نظر پایین‌تر است، می‌فهمیم که عدد مورد نظر بین 50 و 75 است و باید عددی در میانه آن انتخاب کنید. به همین ترتیب ادامه می‌دهیم تا این که به عدد صحیح برسیم. این همان طرز کار الگوریتم جستجوی دودویی است.

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

1 2 3 4 5 6 7 8 9 10

ابتدا میانه لیست را پیدا می‌کنیم. این همان عنصری است که در موقعیت Math.floor((first + last)/2) قرار دارد و first همان اندیس نخست و last نیز اندیس آخر آرایه است. در صورتی که عنصر میانی به صورت کسری باشد به یک عدد کامل گرد می‌شود. عنصر میانی در فهرست فوق 5 است. مقدار مورد جستجو که 9 است بزرگ‌تر از 5 است و از این رو در گام دوم، نیمه بالایی لیست یعنی آرایه زیر را جستجو خواهیم کرد:

6 7 8 9 10

عنصر میانی در این لیست برابر با 8 است. 9 بزرگ‌تر از 8 است و از این رو در گام سوم باید لیست زیر را جستجو کنیم:

9 10

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

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

پیاده‌سازی جستجوی دودویی در جاوا اسکریپت

اینک زمان آن رسیده است که الگوریتم جستجوی دودویی را در جاوا اسکریپت کدنویسی کنیم. یک تابع به نام binarySearch ایجاد می‌کنیم که یک مدار و یک آرایه را به عنوان پارامتر می‌گیرد. این تابع اندیسی را که مقدار مورد نظر در آرایه دارد بازگشت می‌دهد. اگر مقدار را پیدا نکند مقدار 1- بازگشت می‌یابد. پیاده‌سازی آن در جاوا اسکریپت به صورت زیر است:

سخن پایانی

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

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

آشنایی با روش استفاده از جستجوی دودویی چیزی نیست که صرفاً برای یک مصاحبه شغلی مورد نیاز باشد؛ بلکه یک مهارت عملی است که باعث می‌شود کد شما کارایی بیشتری پیدا کند.

اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

میثم لطفی (+)

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

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *