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

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

مقدمه

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

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

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

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

جستجوی خطی

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

Set found to false

Set position to −1

Set index to 0

while found is false and index < number of elements

if list[index] is equal to search value

Set found to true

Set position to index

else Add 1 to index

return position

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

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

function linearSearch(value, list) {

let found = false;

let position = -1;

let index = 0;

while(!found && index < list.length) {

if(list[index] == value) {

found = true;

position = index;

} else {

index += 1;

}

}

return position;

}

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

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

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

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

فیلم آموزش JavaScript ES6 جاوا اسکریپت در فرادرس

کلیک کنید

در این حالت راهبرد شما چه می‌تواند باشد؟ آیا باید اعداد به صورت تصادفی انتخاب شوند؟ آیا باید از 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 است و از این رو می‌توانیم جستجو را متوقف کنیم، چون مقدار مورد جستجو یافت شده است.

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

Set first to 0

Set last to the last index in the list

Set found to false

Set position to −1

while found is false and first is less than or equal to last

Set middle to the index halfway between first and last

if list[middle] equals the desired value

Set found to true

Set position to middle

else if list[middle] is greater than the desired value

Set last to middle − 1

else

Set first to middle + 1

return position

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

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

function binarySearch(value, list) {

let first = 0;//left endpoint

let last = list.length - 1;//right endpoint

let position = -1;

let found = false;

let middle;

while (found === false && first <= last) {

middle = Math.floor((first + last)/2);

if (list[middle] == value) {

found = true;

position = middle;

} else if (list[middle] > value) {//if in lower half

last = middle - 1;

} else {//in in upper half

first = middle + 1;

}

}

return position;

}

سخن پایانی

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

فیلم مجموعه آموزش جاوا اسکریپت JavaScript – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

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

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

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

• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش جاوا اسکریپت (JavaScript)
• مجموعه آموزش‌های مهندسی نرم افزار
• انواع الگوریتم های جستجو و Hash Table — راهنمای جامع
• آموزش تعریف توابع در جاوا اسکریپت (JavaScript)
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
• درخت جستجوی دودویی (BST) — ساختار داده و الگوریتم ها

==