BINARY SEARCH IN C | DATA STRUCTURE | BANGLA VERSION

এমন একটা প্রোগ্রাম বানাতে হবে যেখানে প্রধান শিক্ষক কয়জন ছাত্রকে বহিস্কার করতে চান তাই বলবেন । এবং এরপর তাদের রোল নম্বর কত কত তাও বলে দিবেন । এরপর প্রোগ্রাম অন্তত একজনকে ক্ষমা করে দেয়ার জন্য অনুরোধ জানাবে । এবং এটি বাইনারি সার্চ পদ্ধতি অ্যাপ্লাই করে করতে হবে ।

বাইনারি সার্চ পদ্ধতি যেভাবে অ্যাপ্লাই করে করতে হবে ঃ

বাইনারি সার্চ প্রক্রিয়ার জন্য এ্যরের উপাদানগুলাে মানের উর্ধ বা নিম ক্রমানুসারে সাজানো অবস্থায় থাকতে হয়, প্রয়ােজনে সাজিয়ে নিতে হয়। মনে করা যাক, একটি এ্যরের সংখ্যাগুলাে মানের উর্ধ্ব ক্রমানুসারে সাজানো অবস্থায় আছে । এবং তাতে বিশেষ একটি সংখ্যা আছে কিনা খুঁজে দেখতে হবে। এজন্য সাজানাে এ্যরের মােটামুটি মাঝ বরাবর ২ভাগে বিভক্ত করা হয় ,তারপর কাঙ্ক্ষিত সংখ্যাকে মাঝের সংখ্যার ( যদি সংখ্যাটি এ্যরেকে দুইভাগে ভাগ করে) সাথে তুলনা করা হয়।এক্ষেত্রে কাক্ষিত সংখ্যাটি মাঝের সংখ্যার সমান হলে অ্যালগরিদমের কাজ শেষ। আর যদি তা মাঝের সংখ্যা অপেক্ষা ছােট হয় তাহলে কাক্ষিত সংখ্যাটি এ্যরের প্রথমার্ধে আছে বলে মনে করা হয়। অপর দিকে তা যদি মাঝের সংখ্যা অপেক্ষা বড় হয় তাহলে কাঙিক্ষত সংখ্যাটি এ্যরের দ্বিতীয়ার্ধে আছে বলে মনে করা হয়। এইভাবে কোন অংশে কাক্ষিত সংখ্যাটি আছে তা নিশ্চিত হওয়ার পর উক্ত অংশকে আবার দুইভাগে ভাগ করা হয় এবং উপরােক্ত প্রক্রিয়ায় কাজ ততক্ষণ পর্যন্ত চলতে থাকে যতক্ষণ না সংখ্যাটি খুঁজে পাওয়া যায়। যে অংশের মধ্যে কাঙ্ক্ষিত সংখ্যাকে খুঁজা হয় সেই অংশের সর্ববাম দিকের সংখ্যার সূচকের মান একটি চলকে রাখা হয়। যদি কাঙ্ক্ষিত সংখ্যাটি এ্যরের মধ্যে নাও থাকে তাহলেও এই দুটি সূচকের মানের পরিবর্তন এবং প্রয়ােজনীয় বার্তা প্রদর্শন করে সার্চিং প্রক্রিয়া শেষ করা হয়।

আর এ্যরের মাঝের সংখ্যা( MID )নির্ণয়ের সূত্র হলােঃ MID = INT(BEG + END)/2})।

উদাহরণঃ

মনে করা যাক DATA নামের মধ্যে একটি এ্যরেতে নিম্নের 13টি উপাদান সাজানাে অবস্থায় আছে।11, 22 30. 33, 40, 44, 55, 60, 66, 77, 40, 88, 99 এই arrayতে বিশেষ একটি উপাদান যেমন, 40 আছে কি-না তা খুজে বের করতে বাইনারি সার্চ প্রক্রিয়ার কার্যক্রম নিম্নে বর্ণনা করা হলাে। এখানে, ITEM = 40 এবং BEG ও END বলতে এ্যরের কোন অংশের প্রাথমিক এবং শেষ সংখ্যা বুঝানাে হয়েছে। মাঝখানের সংখ্যাটির অবস্থান নিম্নের সূচকের সাহায্যে বের কর।

MID = INT(BEG + END)/2})

DATA এ্যরেতে ITEM খুঁজার সময় অ্যালগরিদমের প্রত্যেক ধাপে DATA [BEG] এবং DATA [END] এর মান প্রথম বন্ধনীর মধ্যে এবং DATA [MID] এর মান তৃতীয় বন্ধনীর মধ্যে সনাক্ত করা হয়েছে।

নিম্নে এলগরিদমের বিভিন্ন ধাপে BEG,END এবং MID এর মান দেখানাে হলাে।

(1) BEG = 1 এবং END = 13 তাহলে MID = INT(1 + 13)/] = 7, DATA [MID] = 55 ।

(11), 22, 30, 33, 40, 44, [55], 60, 66, 77, 40, 88, (99)

(২) যেহেতু 40<55 তাই END এর মান পরিবর্তিত হয়ে END = MID -1 = 6 হয়, এবং

[MID] = INT[(1 + 6)/2] = 3 অতএব DATA [MID) = 33।

(11), 22, 30, (33), 40, (44), (55), 60, 66, 77, ৪০, ৪৪,(99)

(৩) আবার যেহেতু 40>33, তাই BEG এর মান পরিবর্তন হয়ে MID = INT[(4 + 6)/2] = 5 হয় অতএব DATA [MID] = 40

11, 22, 30, (33), [40], (44), 55, 60, 66, 77, ৪০, ৪৪, 99

অর্থাৎ আমাদের কাঙ্খিত সংখ্যা 40 এ্যরের LOC = 5 তম অবস্থানে আছে।

আবার ITEM = ৪5 ধরে নিম্নে ITEM এর জন্য বাইনারি সার্চ প্রক্রিয়া নিম্নে বর্ণনা করা হলাে।

(১) BEG = 1 এবং END = 13, এবং MID = 7 এবং DATA [MID] = 55 ।

(11), 22, 30, 33, 40, 44, 55], 60, 66, 77, ৪০, ৪৪, (99)

(২) যেহেতু ৪5>77 তাহলে BEG এর মান পরিবর্তন হয়ে BEG = MID+1=8 হয় ।

তাহলে, MID = INT[(৪ + 13)/2] = 10 । অতএব DATA [MID] =77 ।

11, 22, 30, 33, 40, 44, 55, (60), 66, [77], 80, 88, (99)

.৩) আবার যেহেতু 85<77, কাজেই BEG এর মান পরিবর্তন হয়ে BEG = MID+1=11 হয় । তাহলে, MID = INTI(11 + 13)/2] = 12 অতএব DATA [MID] =88 ।

11, 22, 30, 33, 40, 44, 55, 60, 66, 77, (80), [88], (99)

(৪) আবার যেহেতু 85<৪৪ কাজেই END এর মান পরিবর্তিত হয়ে BEG = MID - 1=11 হয় । তাহলে, MID = INT[(11 + 1 1)/2] = 11 অতএব DATA [MID) = 80

11, 22, 30, 33, 40, 44, 55, 60, 66, 77, (80), ৪৪, 99 |

উপরন্তু এবার লক্ষ্যণীয় যে, এখানে BEG = END = MID = 11, হওয়ার পরও কাক্ষিত মান পাওয়া যায় নি । উপরন্তু যেহেতু 85>80, কাজেই BEG এর মান পরিবর্তিত হয়ে BEG = MID + 1 =12 হলে BEG >END সম্ভব নয়, কাজেই 85 সংখ্যাটি উক্ত এ্যরেতে নেই এটা নিশ্চিত।

C Programming Code for Binary Search

প্রদত্ত শর্ত অনুসারে প্রধান শিক্ষককে প্রোগ্রাম জিজ্ঞাসা করবে সে কয় জন ছাত্রকে বহিস্কার করতে চায়? ("how many students do you want to expel” )

printf("How many students do you want to expel :");

scanf("%d",&n);

এরপর প্রধান শিক্ষক তাদের রোল নাম্বারগুলো এক এক করে বলবেন ।

for (i=0; i<n; i++)
 {
 scanf("%d",&arr[i]);
 }

এরপর , যাকে তার কম অপরাধী মনে হয় তাকে ক্ষমা করার জন্য প্রোগ্রাম তাকে অনুরোধ করবে । (“please sir , show ur mercy at least one student”)তখন প্রধান শিক্ষক যাকে ক্ষমা করবেন তার রোল বলবেন ।

printf("please sir , show ur mercy at least one student :");
scanf("%d", &search);

আচ্ছা যদি এমন হয় যে প্রধান শিক্ষক কাউকেই ক্ষমা করবে না বা যাকে ক্ষমা করবে সে কত নম্বরে পজিশনে তাই বের করি তাহলে কেমন হয় ? আর এটি করতে আমাদের বাইনারি সার্চ পদ্ধতি অ্যাপ্লাই করতে হবে ।

তাহলে প্রোগ্রামটি দেখা যাক

/* C Program - Binary Search */

#include<stdio.h>
int main()
{
int n, i, arr[50], search, first, last, middle;
printf("How many students do you want to expel :");
scanf("%d",&n);
printf("Enter %d roll number :", n);
for (i=0; i<n; i++)
{
scanf("%d",&arr[i]);
}
printf("please sir show mercy at least one student  :");
scanf("%d", &search);
first = 0;
last = n-1;
middle = (first+last)/2;
while (first <= last)
{
if(arr[middle] < search)
{
first = middle + 1;
}
else if(arr[middle] == search)
{
printf("%d found at position %d\n", search, middle+1);
break;
}
else
{
   last = middle - 1;
}
middle = (first + last)/2;
}
if(first > last)
{
  printf("Not found! %d is not present in the list.",search);
}

}

Above C Programming Example Output (Element found/ student mercy):