آموزش جاوااسکریپت › انجمن ها › جاوا اسکریپت › جستجوی باینری(Binary Search)در جاوا اسکریپت
برچسب ها: الگوریتم های جستجو جاوا اسکریپت
- این موضوع 0 پاسخ، 1 کاربر را دارد و آخرین بار در 1 سال، 9 ماه پیش بدست مهدی حسن زاده بهروزرسانی شده است.
-
نویسندهنوشتهها
-
مهدی حسن زادهمدیرکل
الگوریتم جستجوی باینری یا همون Binary Search در زیان برنامه نویسی جاوا اسکریپت (javascript) برای آرایه ها استفاده می شود.
به طوری کلی الگوریتم به شکل زیر عمل می کند:
وسط آرایه را پیدا میکنیم.برای اینکار تعداد عناصر را گرفته و آن را بر 2 تقسیم می کنیم. تصور کنید قسمتی از آرایه در سمت چپ و قسمت دیگر در سمت راست قرار دارد.
اگر آیتمی که داریم کمتر از آیتمی است که به دنبال آن هستیم ، باید در سمت راست باشد ، بنابراین می توانیم قسمت سمت راست را به طور کامل کنار بگذاریم.
سپس ما همان عمل را انجام می دهیم ، قسمت سمت راست آرایه را به 2 تقسیم می کنیم ، به مورد میانی نگاه می کنیم و قسمتی از آرایه را دور می اندازیم.
در پایان ، آیتم مورد نظر را دریافت می کنید (یا اگر مورد پیدا نشد ، null برمی گردانید).
در پایان ، اگر آرایه 8 آیتم داشت ، ما حداکثر در 4 مرحله آن را پیدا می کنیم.
اگر آرایه 32 آیتم داشت ، ما در بدترین حالت حداکثر 6 مرحله داریم. در مقایسه با 32 در جستجوی خطی(linear search) ، این یک بهینه سازی بزرگ است!
جستجوی دودویی دارای پیچیدگی O (log n) است.
JavaScript1234567891011121314151617181920212223const binarySearch = (list, item) => {let low = 0let high = list.length - 1while (low <= high) {const mid = Math.floor((low + high) / 2)const guess = list[mid]if (guess === item) {return mid}if (guess > item) {high = mid - 1} else {low = mid + 1}}return null //if not found}الگوریتم جستجوی باینری چطور کار میکنه؟ ما آرایه list و آیتمی را که به دنبال آن هستیم به الگوریتم پاس می دهیم. سپس مقدار low را در ابتدا 0 و مقدار high را با آخرین high موجود در آرایه مقداردهی می کنیم. ما ابتدا به آیتم میانی نگاه می کنیم ، و اگر آن چیزی است که ما به دنبال آن هستیم ، آن را برمی گردانیم و کارمان تمام می شود. در غیر اینصورت ، مقادیر low یا high را طوری تنظیم می کنیم که فقط به قسمت چپ یا راست آرایه نگاه کنند و تا زمانی که مورد را پیدا نکنیم ، روند را تکرار می کنیم.
در اینجا index مربوط به آیتمی که دنبال آن هستیم را برمیگردونیم
JavaScript1234console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4اگر مقداری که به دنیال آن هستیم یافت نشود، null برگشت داده می شود
JavaScript123console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null -
نویسندهنوشتهها