در این پست، الگوریتم جستجوی باینری (Binary Search Algorithm) و الگوریتم جستجوی خطی (Linear Search Algorithm) را مقایسه خواهیم کرد. شبه کد (pseudocode) را نیز برای هر الگوریتم به همراه مثال‌ها و راهنمایی قدم به قدم برای پیاده‌سازی هر یک خواهید دید.

مقدمه

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

تا کنون مطمئناً از الگوریتم جستجویی برای یافتن آیتم‌ها در مجموعه‌ای از داده‌ها بهره برده‌اید. زبان جاوا اسکریپت روش‌های گوناگونی هم‌چون find برای یافتن محل آیتم‌ها در یک آرایه دارد. با این حال این روش‌ها از جستجوی خطی بهره می‌برند. یک الگوریتم جستجوی خطی از ابتدای لیست شروع می‌کند و هر المان را با ارزش (value) جستجو شده مقایسه می‌کند تا پاسخ را بیاید.

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

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

جستجوی خطی یا Linear Search

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

جستجوی باینری یا Binary Search

فرض کنید یک بازی حدس عدد را بازی می‌کنید. از شما خواسته شده است تا عددی میان ۱ الی ۱۰۰ حدس بزنید. اگر عدد شما بالاتر یا پایین‌تر باشد، یک راهنمایی دریافت خواهید کرد.

استراتژی شما چه خواهد بود؟ آیا اعداد را تصادفی انتخاب خواهید کرد؟ آیا ابتدا از ۱ شروع کرده و سپس به عدد ۲ و سپس به عدد ۳ و به همین منوال خواهید رفت تا عدد اصلی را حدس بزنید؟ حتی اگر این امکان را داشته باشید که بی‌نهایت بار حدس بزنید، مطمئناً دوست دارید که عدد اصلی را در کم‌ترین تعداد سعی و خطا حدس بزنید. بنابراین شاید بخواهید با عدد ۵۰ شروع کنید. اگر عدد اصلی بالاتر بود، ۷۵ را حدس خواهید زد. اگر کمتر از ۷۵ بود، یعنی بین ۵۰ و ۷۵ قرار دارد و عدد میانه این بازه را انتخاب خواهید کرد. بدین ترتیب ادامه خواهید داد تا در نهایت به عدد اصلی برسید. این همان شیوه کار الگوریتم جستجوی باینری است.

برخلاف جستجوی خطی، جستجوی باینری از یک لیست چینشی (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