در این پست، الگوریتم جستجوی باینری (Binary Search Algorithm) و الگوریتم جستجوی خطی (Linear Search Algorithm) را مقایسه خواهیم کرد. شبه کد (pseudocode) را نیز برای هر الگوریتم به همراه مثالها و راهنمایی قدم به قدم برای پیادهسازی هر یک خواهید دید.
به عنوان یک برنامهنویس، شما در پی این هستید که بهترین راه حل را برای یک مشکل بیابید تا نه تنها کد شما صحیح باشد، بلکه کارآمد نیز باشد. انتخاب یک الگوریتم زیربهینه (suboptimal) به معنای زمان مورد نیاز بیشتر، پیچیدگی بیشتر برای اتمام عملیات و حتی به معنی توقف عملیات کد است.
تا کنون مطمئناً از الگوریتم جستجویی برای یافتن آیتمها در مجموعهای از دادهها بهره بردهاید. زبان جاوا اسکریپت روشهای گوناگونی همچون find برای یافتن محل آیتمها در یک آرایه دارد. با این حال این روشها از جستجوی خطی بهره میبرند. یک الگوریتم جستجوی خطی از ابتدای لیست شروع میکند و هر المان را با ارزش (value) جستجو شده مقایسه میکند تا پاسخ را بیاید.
در صورتی که تعداد المانها کم باشد، این روش خوبی خواهد بود. اما زمانی که لیستهای بزرگی که حاوی هزاران یا میلیونها المان است را جستجو کنید، به روش بهتری برای یافتن محل آیتمها نیاز خواهید داشت. اینجا است که به جستجوی باینری یا دودویی نیاز پیدا خواهید کرد.
در این مقاله آموزشی، نحوه کارکرد جستجوی باینری و نحوه پیادهسازی این الگوریتم در جاوا اسکریپت را توضیح خواهم داد. نخست، الگوریتم جستجوی خطی را مرور خواهیم کرد.
ابتدا با توصیف نحوه پیادهسازی جستجوی خطی در جاوا اسکریپت شروع خواهیم کرد. یک تابع با نام linearSearch ایجاد خواهیم کرد که یک ارزش (value) از نوع اینتیجر (عدد صحیح) یا استرینگ (string) و همچنین یک آرایه را به عنوان پارامترها قبول میکند. این تابع تمامی المانهای آرایه را برای ارزش (value) جستجو کرده و محل ارزش در صورتی که آن را بیابد را گزارش میکند. اگر ارزش در آرایه پیدا نشد، -۱ را بازگشت خواهد داد. به عنوان مثال، فراخوانی linearSearch(1, [3, 4, 2, 1, 5]) مقدار ۳ را بازگشت خواهد داد و فراخوانی linearSearch(0, [3, 4, 2, 1, 5]) مقدار -۱ را بازگشت میدهد.
این شبه کد برای تابع ما خواهد بود:
Set found to false Set position to −۱ 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; }
مهم است بدانید که الگوریتم جستجوی خطی نیازی به استفاده از یک لیست چینشی (sorted list) ندارد. همچنین این الگوریتم میتواند برای استفاده در سناریوهای مختلفی همچون جستجوی آرایهای از object ها با key، کاستومایز شود. اگر آرایهای از دادههای مشتری دارید که شامل key ها برای اسم کوچک و اسم فامیل باشد، میتوانید جستجو کنید که آیا آرایه دارای مشتری با نام کوچک معینی هست یا نه. در این صورت، به جای بررسی اینکه آیا list[index] برابر با ارزش جستجو شده ما است یا نه، میتوانید list[index].first را بررسی نمایید.
در مثال بالا، از تابع linearSearch برای جستجو در آرایهای پنج المانی استفاده کردم. در بدترین حالت، اگر ارزش جستجو شده در لیست نباشد یا در انتهای لیست باشد، تابع مجبور به پنج بار مقایسه است. به دلیل اینکه آرایه ما بسیار کوچک است، نیازمند بهینهسازی بوسیله استفاده از الگوریتمی متفاوت نخواهیم بود. اما اگر از حد معینی فراتر رویم، دیگر استفاده از الگوریتم جستجوی خطی کارآمد نخواهد بود و اینجا است که باید از الگوریتم جستجوی باینری بهره ببریم.
فرض کنید یک بازی حدس عدد را بازی میکنید. از شما خواسته شده است تا عددی میان ۱ الی ۱۰۰ حدس بزنید. اگر عدد شما بالاتر یا پایینتر باشد، یک راهنمایی دریافت خواهید کرد.
استراتژی شما چه خواهد بود؟ آیا اعداد را تصادفی انتخاب خواهید کرد؟ آیا ابتدا از ۱ شروع کرده و سپس به عدد ۲ و سپس به عدد ۳ و به همین منوال خواهید رفت تا عدد اصلی را حدس بزنید؟ حتی اگر این امکان را داشته باشید که بینهایت بار حدس بزنید، مطمئناً دوست دارید که عدد اصلی را در کمترین تعداد سعی و خطا حدس بزنید. بنابراین شاید بخواهید با عدد ۵۰ شروع کنید. اگر عدد اصلی بالاتر بود، ۷۵ را حدس خواهید زد. اگر کمتر از ۷۵ بود، یعنی بین ۵۰ و ۷۵ قرار دارد و عدد میانه این بازه را انتخاب خواهید کرد. بدین ترتیب ادامه خواهید داد تا در نهایت به عدد اصلی برسید. این همان شیوه کار الگوریتم جستجوی باینری است.
برخلاف جستجوی خطی، جستجوی باینری از یک لیست چینشی (sorted list) استفاده میکند. برای جستجوی یک ارزش، ابتدا ارزش را با المان میانی لیست مقایسه میکنید. اگر برابر باشند، ارزش جستجو شده را یافتهاید. اگر ارزش جستجو شده بزرگتر از المان میانی باشد، نیمه بالایی دادهها را جستجو خواهید کرد. سپس المان میانی این بازه را با ارزش جستجو شده مقایسه میکنید. اگر ارزش جستجو شده کمتر از المان میانی باشد، نیمه پایینی دادهها را جستجو کرده و آن را با المان میانی این بازه پایینی مقایسه خواهید کرد. لیست را مکرراً تا جایی نصف میکنید که المان را بیابید یا هیچ آیتم دیگری برای جستجو نباشد.
برای جستجوی عدد ۹ در این لیست:
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰
بتدا المان میانی را مییابیم. این المان در محل Math.floor((first + last)/2) قرار دارد که first به معنی اولین ایندکس و last به معنی آخرین ایندکس است. عدد را به پایین رند میکنیم تا اگر نتیجه این جمع و تقسیم عددی اعشاری بود، تبدیل به عددی کامل شود. المان میانی این لیست ۵ است. ارزش جستجو شده توسط ما یعنی ۹ بزرگتر از ۵ است و بنابراین این لیست را جستجو میکنیم:
۶ ۷ ۸ ۹ ۱۰
المان میانی این بخش برابر با ۸ است. ۹ بزرگتر از ۸ است پس این لیست را جستجو میکنیم:
۹ ۱۰
المان میانی ۹ است، پس جستجو را در اینجا متوقف میکنیم.
در اینجا شبه کدی را آوردهایم که الگوریتم بالا را برای جستجوی باینری توصیف میکند:
Set first to 0 Set last to the last index in the list Set found to false Set position to −۱ 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 − ۱ else Set first to middle + 1 return position
حال بیایید الگوریتم جستجوی باینری را در جاوا اسکریپت کدنویسی کنیم!
تابعی با نام binarySearch ایجاد میکنیم که یک ارزش و یک آرایه را به عنوان پارامترها قبول میکند. این تابع در صورت یافتن ارزش، ایندکس محلی را بازگشت میدهد که ارزش را در آنجا یافته است و اگر ارزش یافت نشود، -۱ را بازگشت میدهد. این کد پیادهسازی این الگوریتم در جاوا اسکریپت است:
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; }
در این مقاله آموزشی دیدیم که چگونه یک الگوریتم جستجوی خطی و یک الگوریتم جستجوی باینری را پیادهسازی کنیم. الگوریتم جستجوی خطی هم سادهتر است و هم نیازی به آرایه چینشی (sorted array) ندارد. با این حال برای استفاده در آرایههای بزرگ، بسیار ناکارامد است. در بدترین حالت، الگوریتم باید تمامی المانها را در n بار مقایسه جستجو کند (که n تعداد المانها است).
در سمت مقابل، در الگوریتم جستجوی باینری نیاز است تا ابتدا آرایه را مرتب کنیم و همچنین پیادهسازی پیچیدهتری نیز دارد. با این حال حتی اگر هزینه مرتبسازی را در نظر بگیریم، بسیار کارآمدتر است. به عنوان مثال، آرایهای با ۱۰ المان در جستجوی باینری تنها نیاز به ۴ مقایسه دارد، در حالی که جستجوی خطی نیاز به ۱۰ مقایسه خواهد داشت. شاید بگویید دستاورد بزرگی نیست! حال آرایهای با یک میلیون المان در نظر بگیرید. در بدترین حالت، الگوریتم جستجوی باینری تنها نیاز به ۲۰ مقایسه دارد و این عدد را با یک میلیون مقایسه انجام گرفته در الگوریتم جستجوی خطی مقایسه نمایید. دستاورد بزرگی است، نه!
البته دانستن نحوه استفاده از جستجوی باینری چیزی نیست که برای یک مصاحبه شغلی تمرین کنید. اما دانستن آن و پیادهسازی آن مهارتی است که عملکرد کد شما بسیار بهینهتر و کارآمدتر خواهد کرد.
منبع: tutsplus