آموزش جاوااسکریپت انجمن ها جاوا اسکریپت جستجوی باینری(Binary Search)در جاوا اسکریپت

در حال نمایش 1 نوشته (از کل 1)
  • نویسنده
    نوشته‌ها
  • #57387 پاسخ

    الگوریتم جستجوی باینری یا همون Binary Search در زیان برنامه نویسی جاوا اسکریپت (javascript) برای آرایه ها استفاده می شود.

    به طوری کلی الگوریتم به شکل زیر عمل می کند:

    وسط آرایه را پیدا میکنیم.برای اینکار تعداد عناصر را گرفته و آن را بر 2 تقسیم می کنیم. تصور کنید قسمتی از آرایه در سمت چپ و قسمت دیگر در سمت راست قرار دارد.

    اگر آیتمی که داریم کمتر از آیتمی است که به دنبال آن هستیم ، باید در سمت راست باشد ، بنابراین می توانیم قسمت سمت راست را به طور کامل کنار بگذاریم.

    سپس ما همان عمل را انجام می دهیم ، قسمت سمت راست آرایه را به 2 تقسیم می کنیم ، به مورد میانی نگاه می کنیم و قسمتی از آرایه را دور می اندازیم.

    در پایان ، آیتم مورد نظر را دریافت می کنید (یا اگر مورد پیدا نشد ، null برمی گردانید).

    در پایان ، اگر آرایه 8 آیتم داشت ، ما حداکثر در 4 مرحله آن را پیدا می کنیم.

    اگر آرایه 32 آیتم داشت ، ما در بدترین حالت حداکثر 6 مرحله داریم. در مقایسه با 32 در جستجوی خطی(linear search) ، این یک بهینه سازی بزرگ است!

    جستجوی دودویی دارای پیچیدگی O (log n) است.

    الگوریتم جستجوی باینری چطور کار میکنه؟ ما آرایه list و آیتمی را که به دنبال آن هستیم به الگوریتم پاس می دهیم. سپس مقدار low را در ابتدا 0 و مقدار high را با آخرین high موجود در آرایه مقداردهی می کنیم. ما ابتدا به آیتم میانی نگاه می کنیم ، و اگر آن چیزی است که ما به دنبال آن هستیم ، آن را برمی گردانیم و کارمان تمام می شود. در غیر اینصورت ، مقادیر low یا high را طوری تنظیم می کنیم که فقط به قسمت چپ یا راست آرایه نگاه کنند و تا زمانی که مورد را پیدا نکنیم ، روند را تکرار می کنیم.

    در اینجا index مربوط به آیتمی که دنبال آن هستیم را برمیگردونیم

    اگر مقداری که به دنیال آن هستیم یافت نشود، null برگشت داده می شود

در حال نمایش 1 نوشته (از کل 1)
پاسخ به: جستجوی باینری(Binary Search)در جاوا اسکریپت
اطلاعات شما: