خوارزم البحث الثنائي Binary Search Algorithm:
تقوم فكرة البحث الثنائي على تقسيم المصفوفة إلى نصفين واستبعاد النصف الذي لا ينتمي إليه المفتاح key الذي نبحث عنه، كيف ذلك؟
عن طريق تحديد العنصر الذي يقع في منتصف هذه المصفوفة، ثم نقارن هذا العنصر مع المقتاح الذي نبحث عنه كالتالي (تذكر أن مصفوفتنا مرتبة تصاعدياً أو تنازلياً):

سيساعدك المثال التالي على فهم الطريقة إن شاء الله:
نفرض أننا نبحث عن عناصر مختلفة في هذه المصفوفة:

Array[]={0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28}

تابع في هذا الفلاش التسلسل في البحث عن عناصر مختلفة:

والسؤال الآن: كيف نكتب code يمثل هذا الخوارزم بالجافا أو السي؟!
وللإجابة على هذا السؤال سيصادفنا تساؤل آخر: كيف نرتب المصفوفة تصاعدياً او تنازلياً؟!
والإجابة:
لترتيب المصفوفة فهناك عدة خوارزميات للترتيب منها على سبيل المثال: (Bubble sort, sorting by Selection, sorting by Insertion, Shell sort, & Quick sort).
ولا مجال لذكرها الآن، حيث سنعتمد في الـcode على ترتيبنا نحن للمصفوفة بشكل صحيح.
والآن، لنستعرض معاً code يطبق تكنيك binary search على مصفوفة ذات عناصر رقمية بلغة الجافا، حيث أن j=high، i=low, & k=middle :

// Binary search of an array
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.text.*;

public class BinarySearch extends JApplet
implements ActionListener {
JLabel enterLabel, resultLabel;
JTextField enter, result;
JTextArea output;

int a[];
String display = "";

public void init()
{
Container c = getContentPane();
c.setLayout( new FlowLayout() );

enterLabel = new JLabel( "Enter key" );
c.add( enterLabel );

enter = new JTextField( 5 );
enter.addActionListener( this );
c.add( enter );

resultLabel = new JLabel( "Result" );
c.add( resultLabel );

result = new JTextField( 22 );
result.setEditable( false );
c.add( result );

output = new JTextArea( 6, 60 );
output.setFont(
new Font( "Courier", Font.PLAIN, 12 ) );
c.add( output );

// create array and fill with even integers 0 to 28
a = new int[ 15 ];

for ( int i = 0; i < a.length; i++ )
a[ i ] = 2 * i;
}

public void actionPerformed( ActionEvent e )
{
String searchKey = e.getActionCommand();

// initialize display string for the new search
display = "Portions of array searchedn";

// perform the binary search
int element = binarySearch( a, Integer.parseInt( searchKey ) );

output.setText( display );

if ( element != -1 )
result.setText("Found value in element " + element );
else
result.setText( "Value not found" );
}

// Binary search
public int binarySearch( int array[], int key )
{
int low = 0; // low subscript
int high = array.length - 1; // high subscript
int middle; // middle subscript

while ( low <= high ) {
middle = ( low + high ) / 2;

// The following line is used to display the part
// of the array currently being manipulated during
// each iteration of the binary search loop.
buildOutput( low, middle, high );

if ( key == array[ middle ] ) // match
return middle;
else if ( key < array[ middle ] )
high = middle - 1; // search low end of array
else
low = middle + 1; // search high end of array
}

return -1; // searchKey not found
}

// Build one row of output showing the current
// part of the array being processed.
void buildOutput( int low, int mid, int high )
{
DecimalFormat twoDigits = new DecimalFormat( "00" );

for ( int i = 0; i < a.length; i++ ) {
if ( i < low || i > high )
display += " ";
else if ( i == mid ) // mark middle element in output
display += twoDigits.format( a[ i ] ) + "* ";
else
display += twoDigits.format( a[ i ] ) + " ";
}

display += "n";
}
}

عدد مرات البحث في أي مصفوفة عن عنصر محدد باستخدام الـBinary Search:
لو تسائلنا عن أقصى عدد من مرات البحث باستخدام الـBinary Search في أي مصفوفة، لوجدنا أنه يُعطى من إيجاد القوة التي يرفع إليها رقم 2 كي يطعينا العدد الذي يزيد عن عناصر المصفوفة بواحد. أي أنه أول قوة لـ2 والتي تُعطي رقم أكبر من عدد عناصر المصفوفة بواحد.
ففي مثالنا: استخدمنا مصفوفة من 15 عنصر، نلاحظ ان العدد الذي يزيد على عدد عناصر المصفوفة بواحد، أي العدد 16 ينتج من القوة الرابعة لرقم2 (2^4=16) وذلك يعني اننا نحتاج على الأكثر لأربع مرات مقارنة في الـBinary Search حتى نجد العنصر الذي نبحث عنه! فمن الممكن أن نجده من أول مرة في المقارنة، ومن الممكن أن نجده في ثاني مرة، أو ثالث مرة أو رابع مرة.. أو أن يكون غير موجود في المصفوفة!
وفي مثال آخر: لو بحثنا في مصفوفة تحوي 1024 عنصر، سنحتاج إلى 10 مرات للمقارنة كحد أقصى، ونعرف ذلك بتكرار قسمة عدد العناصر على رقم 2 إلى أن نصل إلى العدد واحد في خارج القسمة (وسبب ذلك هو أننا بعد كل مقارنة نقوم بإلغاء نصف عناصر المصفوفة من الاعتبار)، فبتكرار قسمة 1024 على رقم 2 نحصل على القيم التالية على الترتيب: 512، 256، 128، 64، 32، 16، 8، 4، 2، ورقم 1. نلاحظ أن العدد 1024 (2^10) قسم على رقم 2 عشر مرات حتى حصلنا على العدد 1.
نستنتج من ذلك، أن القسمة على اثنين تقابل مرة واحدة من المقارنة في الـBinary Search Algorithm. فمصفوفة بـ 1048576 (2^20) عنصر تستلزم على الأكثر 20 مرة من المقارنة حتى نجد العنصر الذي نبحث عنه، ومصفوفة تحوي بليون عنصر، تستلزم على الأكثر إلى 30 مرة من المقارنة حتى نجد العنصر المطلوب فيها!
ترى، كم يوفر لنا هذا التكنيك من الوقت في البحث؟.. فقط 30 مرة من البحث بين بليون عنصر لنجد ضالتنا!!.. إنه تكنيك عبقري فعلاً