جستجوی باینری(Binary Search)در جاوا اسکریپت

[مهدی حسن زاده]

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

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

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

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

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

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

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

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

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

JavaScript

const binarySearch = (list, item) => { let low = 0 let high = list.length - 1 while (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 }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

const binarySearch = (list, item) => {     let low = 0     let high = list.length - 1        while (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 مربوط به آیتمی که دنبال آن هستیم را برمیگردونیم

JavaScript

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0 console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

1 2 3 4

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0 console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

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

JavaScript

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

1 2 3

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

[نویسنده]

نوشته‌ها