پیاده‎سازی الگوریتم Binary Search در زبان برنامه‌نویسی جاوااسکریپت

دنیای دولوپرها دنیای حل مسائلی است که نه‌تنها باید برای‌شان راه‌حلی صحیح پیدا کرد بلکه در صورت امکان باید آن راه‌حل بهینه نیز باشد. در واقع، اگر یک دولوپر برای مسأله‌ای الگوریتمی را انتخاب کند که به اندازۀ کافی بهینه نباشد، منجر به کدی می‌شود که یا پیچیده است یا به کُندی اجرا خواهد شد و یا از این‌ها بدتر، منجر به کِرَش کردن برنامه خواهد شد.

عمل جستجو در آرایه‌ها و لیست‌ها در حوزهٔ توسعهٔ نرم‌افزار بسیار پرکاربرد است و معمولاً متدهایی برای منظور در زبان‌های برنامه‌نویسی مختلف در نظر گرفته شده‌اند و در زبان جاوااسکریپت نیز متدهای زیادی برای این کار وجود دارد اما نکته‌ای که باید مد نظر قرار داد این است که این متدهای پیش‌فرض غالباً از Linear Search Algorithm استفاده می‌کنند. سازوکار این الگوریتم بدین صورت است که همۀ اعضای آرایه یا لیست به ترتیب با آیتمی که قرار است پیدا شود مقایسه می‌شوند و با پیدا شدن آیتم مورد نظر و یا در صورتی که هیچ آیتمی برای مقایسه باقی نمانده باشد، کار این الگوریتم هم پایان می‌یابد. در این روش زمانی که تعداد عناصر موجود در لیست زیاد نباشد مشکلی وجود ندارد اما در شرایطی که لیست بزرگی داشته باشیم، که مثلاً دارای چند هزار یا چند میلیون عضو است، باید از یک الگوریتم سریع‌تر نظیر Binary Search Algorithm استفاده کنیم.

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

پیاده‌سازی الگوریتم Linear Search در جاوااسکریپت
برای پیاده‌سازی Linear Search در جاوااسکریپت فانکشنی به نام ()linearSearch می‌سازیم که پارامترهای آن شامل یک مقدار (Value) از نوع اینتجر یا استرینگ و همچنین آرایه‌ای از مقادیر مختلف است که باید داخل آن عمل جستجو را انجام دهیم و خروجی این فانکشن یک عدد صحیح است که در صورت وجود داشتن مقدار مد نظر، مکان قرارگیری آن در آرایه و در غیر این صورت عدد 1- خواهد بود.

برای مثال، اگر ([linearSearch(1, [3, 4, 2, 1, 5 را صدا بزنیم، از آنجا که عدد 1 در جایگاه سوم قرار گرفته است (اولین خانۀ آرایه جایگاه صفر را دارد) پس به عنوان خروجی باید عدد 3 ریترن شود و اگر ([linearSearch(0, [3, 4, 2, 1, 5 را صدا بزنیم چون عدد ۰ در این آرایه وجود ندارد، 1- به عنوان خروجی ریترن می‌شود.

Pseudocode یا «شِبه‌کد» بیانی از الگوریتم است که معمولاً شبیه به یک زبان برنامه‌نویسی نوشته می‌شود اما قابل‌اجرا در کامپیوتر نیست بلکه برای آسان نمودن درک و فهم یک الگوریتم برای دولوپرها مورد استفاده قرار می‌گیرد. حال با این توضیحات، سودوکد الگوریتم فوق عبارت است از:

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

در کد زیر الگوریتم Linear Search در قالب فانکشنی با نام ()linearSearch با زبان جاوااسکریپ پیاده‌سازی شده است:

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;
}

در تفسیر کدهای فوق باید گفت ابتدا به ساکن دست به تعریف متغیرهای position ،found و index زده‌ و مقادیر پیش‌فرضی هم برای تک‌تک آن‌ها در نظر گرفته‌ایم و این در حالی است که الگوریتم اصلی داخل بلوک while نوشته شده است که به عنوان شرط بلوک while گفته‌ایم مادامی که مقدار متغیر found برابر با true نباشد و مقدار متغیر index از طول آرایهٔ list کوچک‌تر باشد، جستجو باید ادامه یابد.

در ادامه، با استفاده از یک دستور شرطی if تست کرده‌ایم ببینیم که آیا اندیس در نظر گرفته شده برای آرایهٔ []list برابر با مقدار value است یا خیر (به عبارتی، در دور اول این قضیه تست می‌شود که آیا اندیس صِفرم آرایهٔ list برابر با value می‌باشد یا خیر.) اگر پاسخ true بود، دستورات داخل بلوک if انجام می‌شوند که عبارتند از تغییر مقدار پیش‌فرض متغیر found از false به true و اختصاص مقدار در نظر گرفته شده برای index به متغیر position و در غیر این صورت وارد بلوک else می‌شویم که در این بخش مقدار قبلی متغیر index با عدد ۱ جمع می‌شود و در نهایت و پس از پایان یافتن جستجو در آرایهٔ ورودی، مقدار متغیر position ریترن می‌شود.

نکتۀ قابل‌توجه در Linear Search (جستجوی خطی) این است که مرتب بودن لیست ورودی برای این الگوریتم اهمیتی ندارد مضاف بر اینکه در سناریوهای مختلف می‌توانیم این الگوریتم را مختص به آن سناریو تغییر دهیم به طوری که اگر مثلاً لیستی از یک نوع آبجکت داریم که دارای یک یا چند عضو کلیدی است، می‌توانیم با استفاده از آن کلید/کلیدها به دنبال آیتم مورد نظرمان بگردیم. 

در دو مثالی که در بخش قبل برای سودوکد آوردیم، آرایه‌ای که به عنوان آرگومان ورودی فانکشن ()linearSearch در نظر گرفتیم 5 عضو داشت که در بدترین حالت، یعنی زمانی که آیتم مورد نظر وجود نداشته باشد و یا در شرایطی که آن آیتم در آخرین جایگاه قرار گرفته باشد، 5 عمل مقایسه انجام خواهد شد. در واقع، در این مثال‌ها چون آرایۀ کوچکی را در نظر گرفته‌ایم نیازی به بهینه ساختن کد با یک الگوریتم بهتر نداریم اما اگر آرایه بزرگ‌تر شود، از یک جا به بعد دیگر این الگوریتم جوابگوی نیاز ما نخواهد بود و باید از الگوریتمی بهتر مثل Binary Search استفاده نماییم.

پیاده‌سازی Binary Search در جاوااسکریپت
فرض کنید که قرار است نوعی بازی انجام دهیم که حول حدس زدن اعداد می‌چرخد و در این بازی عددی در یک بازۀ مشخص، مثلاً بین 1 تا 100، در نظر گرفته می‌شود و ما به تعداد محدود می‌توانیم حدس بزنیم تا آن عدد را پیدا کنیم. هر بار که عددی را حدس می‌زنیم، اگر درست نباشد به عنوان راهنمایی گفته می‌شود که عددِ مورد نظر از عددی که حدس زده‌ایم کمتر یا بیشتر است.

در این بازی می‌توانیم الگوریتم «حدسِ تصادفی» را به کار ببریم بدین صورت که هر عددی به ذهن‌مان رسید بگوییم و ببینیم درست است یا خیر اما در عین حال الگوریتم دیگر این است که از عدد 1 شروع کنیم و یکی‌یکی بشماریم تا عدد مورد نظر را پیدا کنیم که این حالت شبیه به Linear Search است. همچنین استراتژی دیگری که می‌توانیم در نظر بگیریم تا با تعداد حدس کمتری به نتیجه برسیم، انتخاب عدد میانی (در این مثال عدد 50) است به طوری که اگر عدد در نظر گرفته شده بیشتر از 50 باشد، اعداد 1 تا 49 را حذف خواهیم کرد و این بار عدد میانی 50 تا 100 که می‌شود 75 را به عنوان حدس‌مان انتخاب می‌کنیم و به همین ترتیب با توجه به راهنمایی‌هایی که می‌گیریم، عدد بعدی را طوری انتخاب می‌کنیم که در میان بازۀ بالا یا پایین قرار بگیرد تا در نهایت به جواب برسیم. این روش کار در واقع همان الگوریتم Binary Search است.

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

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

1 2 3 4 5 6 7 8 9 10

طبق الگوریتمی که توضیح داده شد، ابتدا عدد میانی را با استفاده از کد (Math.floor((first + last) / 2 پیدا می‌کنیم. در این کد متغیر first ایندکسِ (اندیس) اولین عدد و last ایندکسِ آخرین عدد در این آرایه است و از آنجا که ایندکس آرایه نمی‌تواند یک عدد اعشاری باشد، از فانکشن ()floor که توسط طراحان زبان جاوااسکریپت در این زبان تعبیه شده است استفاده می‌کنیم که حاصل عبارت 2 / (first + last) را در صورت اعشاری بودن به یک عدد صحیح رو به پایین رُند می‌کند (مثلاً 3/5 را تبدیل به 3 می‌کند.) در لیست مذکور، عدد میانی 5 است و مقداری که به دنبالش می‌گردیم 9 است که از 5 بزرگ‌تر است و از همین روی در نیمۀ بالایی لیست جستجو می‌کنیم که عبارت است از:

6 7 8 9 10

عدد میانیِ این لیست 8 است و 9 از 8 بزرگ‌تر است فلذا دوباره در نیمۀ بالایی می‌گردیم که لیست زیر می‌شود:

9 10

عدد میانی در این لیست 9 است و این همان عددی است که به دنبالش می‌گردیم. در نتیجه جستجو به پایان می‌رسد.

آنچه برای نحوهٔ عملکرد الگوریتم Binary Search توضیح دادیم را می‌توان در قالب یک سودوکد به صورت زیر نوشت:

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

برای پیاده‌سازی Binary Search با استفاده از جاوااسکریپت، فانکشنی به نام ()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;
}

در تفسیر اسکریپت فوق، باید گفت که پیش از هر چیز با استفاده از کلیدواژهٔ let از خط دوم تا ششم اقدام به تعریف پنج متغیر کرده‌ایم. به عنوان شرط بلوک while هم گفته‌ایم چنانچه مقدار متغیر found برابر با false بود و مقدار متغیر first کوچک‌تر یا مساوی با مقدار متغیر last بود، چرخش ادامه یابد.

داخل بلوک while هم پیش از هر چیز، مقدار متغیر middle را یافته‌ایم بدین صورت که با استفاده از کلاس پیش‌فرض زبان جاوااسکریپت تحت عنوان Math گفته‌ایم مقدار رُند حاصل‌جمع متغیرهای first و last تقسیم‌ بر عدد ۲ به عنوان مقدار متغیر middle در نظر گرفته شود. سپس با استفاده از یک دستور شرطی چک کرده‌ایم ببینیم آیا آرایهٔ []list با اندیسی همچون middle برابر با مقدار پارامتر ورودی value می‌باشد یا خیر که اگر این مقدار true بود، وارد بلوک if شده و مقدار متغیر found را از false به true تغییر می‌دهیم سپس مقدار متغیر middle را برای متغیر position در نظر می‌گیریم.

اما اگر خروجی این شرط false بود، وارد بلوک else if می‌شویم تا شرط دیگری را تست کنیم مبنی بر اینکه اگر آرایهٔ []list با اندیس middle بزرگ‌تر مقدار value بود، ۱ واحد از مقدار متغیر middle کسر کرده و نتیجه را به متغیر last اختصاص دهیم.

حال اگر نه پاسخ به شرط if و نه پاسخ به شرط else if برابر با true بود، وارد بلوک else خواهیم شد که در آن دستور داده‌ایم ۱ واحد به مقدار متغیر middle اضافه شده و حاصل‌جمع به عنوان مقدار متغیر first در نظر گرفته شود و در نهایت هم پس از تکمیل فرآیند مقدار متغیر position ریترن خواهد شد.

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

در مقابل، الگوریتم Binary Search نیاز دارد تا لیست ورودی حتماً مرتب‌شده باشد و پیاده‌سازی آن نیز کمی پیچیده‌تر است اما حتی با در نظر گرفتن هزینه‌ای که برای مرتب کردن آرایه تحمیل می‌شود از یکسو و همچنین صرف زمان برای کدنویسی آن از سوی دیگر، این الگوریتم سریع‌تر از جستجویِ خطی است. برای مثال، اگر یک آرایه با 10 عضو داشته باشیم، در Binary Search حداکثر 4 مقایسه انجام می‌دهیم و در الگوریتم Linear Search تعداد مقایسه‌ها 10 بار خواهد بود که شاید تفاوت زیادی با Binary Search نداشته باشد اما برای یک آرایه با یک میلیون عضو، استفاده از الگوریتم Binary Search حداکثر منجر به 20 عمل مقایسه می‌شود که نسبت به Linear Search که حداکثر یک میلیون مقایسه انجام خواهد داد پیشرفت قابل‌توجهی است!

در آخر باید گفت که مهارت استفاده از Binary Search تنها برای نشان دادن دانش‌تان در یک مصاحبۀ کاری نیست بلکه این مهارت می‌تواند منجر به نوشتن کدی بهینه شود که در نهایت پرفورمنس اپلیکیشن شما را ارتقاء خواهد بخشید.