البحث الثنائي

البحث الخطّي يمرّ على العناصر واحدًا واحدًا، فإذا كان عندك مليون عنصر احتجت إلى مليون مقارنة، أما إن كانت المصفوفة مرتّبة فتكفيك عشرون مقارنة.

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

وانتبه إلى أمرين، الأول أن تكتب الشرط while (lo <= hi) بالمساواة لأنك بدونها تفوّت آخر خانة، والثاني أن تحسب الوسط بـ Math.floor((lo + hi) / 2).