البحث الثنائي (1) Binary Search

بسم الله الرحمن الرحيم

في محاولة لتوضيح طريقة من أسرع طرق البحث في البرمجة، سيفيدك أخي القارئ هذا الدروس بإذن الله

طريقة البحث الثنائي Binary Search:

يصادف المبرمج دوماً العمل مع كمية بيانات كبيرة مخزنة في مصفوفة، ومن الضروري أن يستخدم تكنيك معين يحدد له ما إذا كان العنصر الذي يبحث عنه key ينتمي إلى هذه المصفوفة أم لا! هذا التكنيك يطلق عليه "البحث" وله عدة أنواع، من أشهرها وأكثرها فاعلية طريقة البحث الثنائي.

ولكي نطبق أحد خوارزميات الـBinary Search على مصفوفة ما نتبع الخطوات البسيطة التالية:

الخطوة الأولى والأهم والتي لا يمكن تطبيق الـBinary Search لولاها هي:
ترتيب المصفوفة تصاعدياً أو تنازلياً أو أبجدياً على حسب نوع البيانات المخزنة فيها!
تحديد أول عنصر في المصفوفة ولنسمه i، وآخر عنصر فيها ولنسمه مثلاً j.
تحديد العنصر الذي يقع في منتصف هذه المصفوفة ولنسمه k.
بعد ذلك يمكننا تطبيق تكنيك البحث الثنائي على مصفوفتنا، وهناك عدة خوارزميات للبحث الثنائي، سأشرح أحدها في هذا الدرس على مصفوفة ذات بيانات رقمية إن شاء الله. وفي الدرس الثاني سنتعرف على المكتبة الجاهزة والتي توفرها الجافا لتطبيق الـBinary Search على مصفوفة ذات بيانات حرفية strings بإذن الله.

خوارزم البحث الثنائي Binary Search Algorithm:

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

إذا كان يساويه نكون قد وجدنا العنصر الذي نبحث عنه.

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

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

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

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

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";
}
}


وإذا أحببت أن تطلع على الكود بلغة السي، تفضل بزيارة الوصلة التالية:http://www.c4arab.com/showlesson.php?lesid=1496

أما إذا أحببت أن تطلع على خوارزم آخر للـBinary search، تفضل بزيارة هذه الوصلة:http://www.c4arab.com/showlesson.php?lesid=1498

عدد مرات البحث في أي مصفوفة عن عنصر محدد باستخدام الـ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 مرة من البحث بين بليون عنصر لنجد ضالتنا!!.. إنه تكنيك عبقري فعلاً

تابعنا في الدرس الثاني كي تتعرف على المكتبة الجاهزة والتي توفرها الجافا لتطبيق الـBinary Search على مصفوفة ذات عناصر حرفية strings.