خوارزميات جافا سكريبت: بحث ثنائي

يفترض البحث الثنائي أن المصفوفة (أو أي بنية بيانات أخرى) التي تبحث فيها مرتبة.

نبدأ بالمصفوفة والعنصر الذي نحتاج إلى البحث عنه.

ننظر إلى منتصف المصفوفة. نأخذ عدد العناصر ونقسمها على 2. تخيل أن لدينا جزءًا من المصفوفة على اليسار والجزء الآخر على اليمين.

إذا كان العنصر الذي لدينا أقل من العنصر الذي نبحث عنه ، فيجب أن يكون في الجزء الأيمن ، حتى نتمكن من التخلص تمامًا من الجزء الموجود على اليمين.

ثم نقوم بنفس الإجراء ، ونقسم الجزء الأيمن من المصفوفة إلى 2 ، وننظر إلى العنصر الأوسط ، ونرمي جزءًا من المصفوفة.

في النهاية ، ستحصل على العنصر (أو ستعودnullإذا لم يتم العثور على العنصر).

في النهاية ، إذا كانت المصفوفة تحتوي على 8 عناصر ، فسنجد العنصر في 4 خطوات على الأكثر.

إذا كانت المصفوفة تحتوي على 32 عنصرًا ، فلدينا 6 خطوات كحد أقصى في أسوأ الحالات. مقارنة بـ 32 في البحث الخطي ، يعد هذا تحسينًا كبيرًا!

البحث الثنائي لهO(log n) تعقيد.

إليك تنفيذ محتمل لها:

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]

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">===</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">mid</span>
}

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">&gt;</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#a6e22e">high</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
} <span style="color:#66d9ef">else</span> {
  <span style="color:#a6e22e">low</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
}

}

return null //if not found }

كيف يعمل هذا؟ نحصل علىlistالمصفوفة وقيمة العنصر التي نبحث عنها. ثم نقوم بتهيئة ملفlowالقيمة عند 0 مبدئيًا ، وhighقيمة الفهرس الأخير في القائمة. ننظر أولاً إلى العنصر الأوسط ، وإذا كان هو ما نبحث عنه ، فإننا نعيده ، وقد انتهينا. إذا لم يكن كذلك ، فقمنا بتعيينlowأوhighالقيم للنظر فقط إلى الجزء الأيسر أو الأيمن من المصفوفة ، ونكرر العملية حتى نجد العنصر.

نعيد فهرس العنصر في المصفوفة:

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

سوف نعودnullإذا لم يتم العثور على العنصر:

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

المزيد من دروس js: