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

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

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

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

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