তামিম শাহরিয়ার সুবিন-এর লেখা কম্পিউটার প্রোগ্রামিং ২য় খণ্ড প্রকাশ করেছে দ্বিমিক প্রকাশনী। বিস্তারিত জানতে এখানে ক্লিক করুন।

[প্রোগ্রামিং বইঃ অধ্যায় আট] বাইনারি সার্চ।

একটি সহজ খেলা দিয়ে শুরু করা যাক। এটি খেলতে দুজন দরকার। একজন মনে মনে একটি সংখ্যা ধরবে। আর দ্বিতীয়জন কিছু প্রশ্ন করে সেই সংখ্যাটি বের করবে। তবে 'তোমার সংখ্যাটি কত?' - এমন প্রশ্ন কিন্তু সরাসরি করা যাবে না। প্রশ্নটি হচ্ছে:
সংখ্যাটি কি N (একটি সংখ্যা)-এর চেয়ে বড়, ছোট নাকি সমান?

আর সংখ্যাটি কিন্তু একটি নির্দিষ্ট সীমার মধ্যে হতে হবে (যেমন 1 থেকে 100, 10 থেকে 1000, -1000 থেকে 100000)।
এখন ধরা যাক, প্রথমজন যে সংখ্যাটি ধরেছে সেটি 1 থেকে 1000-এর ভেতর একটি সংখ্যা। তাহলে কিন্তু সর্বোচ্চ এক হাজার বার 'সংখ্যাটি কি N-এর সমান?' প্রশ্নটি করে সেটি বের করে ফেলা যায়। (সংখ্যাটি কি 1? সংখ্যাটি কি 2? ... সংখ্যাটি কি 999?, সংখ্যাটি কি 1000?)। এভাবে প্রশ্ন করতে থাকলে সংখ্যাটি অবশ্যই বের হবে। তবে ভাগ্য খারাপ হলে এক হাজার বার ওই প্রশ্নটি করতে হবে।

কিন্তু আমাদের তো এত সময় নেই। ধরা যাক, 1 থেকে 1000-এর ভেতর ওই সংখ্যাটি হচ্ছে 50। তাহলে আমাদের প্রথম প্রশ্ন হবে:
১) সংখ্যাটি কি 500-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।
২) সংখ্যাটি কি 250-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।
৩) সংখ্যাটি কি 125-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।
৪) সংখ্যাটি কি 62-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।
৫) সংখ্যাটি কি 31-এর চেয়ে বড়, ছোট নাকি সমান? বড়।
৬) সংখ্যাটি কি 46-এর চেয়ে বড়, ছোট নাকি সমান? বড়।
৭) সংখ্যাটি কি 54-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।
৮) সংখ্যাটি কি 50-এর চেয়ে বড়, ছোট নাকি সমান? সমান।
আমরা মাত্র আটটি প্রশ্ন করেই সংখ্যাটি পেয়ে গেছি!

তোমরা নিশ্চয়ই পদ্ধতিটি বুঝে ফেলেছ? প্রতিবার প্রশ্ন করে সংখ্যাটি যে সীমার মধ্যে আছে তাকে অর্ধেক করে ফেলা হয়েছে। খেলা শুরুর সময় সীমাটি ছিল 1 থেকে 1000। তারপর সেটি হয়েছে 1 থেকে 500। তারপর 1 থেকে 250, 1 থেকে 125, 1 থেকে 62, 31 থেকে 62, 46 থেকে 62, 46 থেকে 54।

সংখ্যা খুঁজে বের করার এই পদ্ধতিকে বলে বাইনারি সার্চ। চলো আমরা তাহলে অ্যালগরিদমটি লিখার চেষ্টা করি:
বাইনারি সার্চ (low, high, N): (শুরুতে আমাদের তিনটি সংখ্যা জানতে হবে, সংখ্যাটির নিম্নসীমা (low), উচ্চসীমা (high) এবং সেই সংখ্যা (N))
ধাপ 1: mid = (low + high) / 2
ধাপ 2: যদি mid এবং N-এর মান সমান হয় তবে ধাপ 5-এ যাও।
ধাপ 3: যদি N, mid-এর চেয়ে বড় হয়, তাহলে low = mid + 1. ধাপ 1-এ যাও।
ধাপ 4: যদি N, mid-এর চেয়ে ছোট হয়, তাহলে high = mid - 1. ধাপ 1-এ যাও।
ধাপ 5: সংখ্যাটি পেয়ে গেছি (mid)।

এখন আমরা দেখব একটি অ্যারে থেকে কীভাবে বাইনারি সার্চ করে কোনো সংখ্যা খুঁজে বের করতে হয়। অ্যারেতে কিন্তু সংখ্যাগুলো ছোট থেকে বড় কিংবা বড় থেকে ছোট ক্রমানুসারে থাকতে হবে। নইলে বাইনারি সার্চ ব্যবহার করা যাবে না। কারণটি কি কেউ বলতে পারো?
প্রথমে আমরা একটি ইন্টিজার অ্যারে নিই যেখানে সংখ্যাগুলো ছোট থেকে বড় ক্রমানুসারে সাজানো আছে।
int ara[] = {1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33 83, 87, 97, 99, 100};

এখন বলো তো low আর high-এর মান কত হবে? low = 1 এবং high = 100 ? ঠিকই ধরেছ কিন্তু এখানে একটু সমস্যা আছে। আমরা এখানে সব সংখ্যার মধ্যে খুঁজব না, বরং অ্যারের ইনডেক্সের মধ্যে খুঁজব। আর অ্যারের ইনডেক্সগুলো ক্রমানুসারে থাকে বলেই অ্যারেতে বাইনারি সার্চ করা যায়। এখানে ara-এর সর্বনিম্ন ইনডেক্স হচ্ছে 0 এবং সর্বোচ্চ ইনডেক্স হচ্ছে 15। তাহলে আমরা দুটি ভেরিয়েবলের মান নির্দিষ্ট করে দিই -
low_indx = 0;
high_indx = 15;
যে সংখ্যাটি খুঁজব ধরা যাক সেটি হচ্ছে 97।
num = 97;

তোমাদের অনেকেই হয়তো ভাবছ, num সংখ্যাটি যদি ara-তে না থাকে তখন কী হবে? সেটিও আমরা দেখব। সংখ্যাটি যদি খুঁজে পাওয়া না যায় তবে সেটি জানিয়ে দেওয়ার ব্যবস্থা রাখতে হবে আমাদের প্রোগ্রামে।

আমাদের যেহেতু খোঁজার কাজটি বারবার করতে হবে, আমাদেরকে একটি লুপ ব্যবহার করতে হবে। লুপের ভেতর আমরা খোঁজাখুঁজি করব আর সংখ্যাটি পেয়ে গেলে (কিংবা সংখ্যাটি নেই সেটি নিশ্চিত হলে) আমরা লুপ থেকে বের হয়ে যাব।
 while(1) {  
     mid_indx = (low_indx + high_indx) / 2;       
     if(num == ara[mid_indx]) {  
         /* num যদি ara[mid_indx]-এর সমান হয়, তবে সেটি আমরা পেয়ে গেছি */  
         break;  
     }       
     if(num < ara[mid_indx]) {       
         /* num যদি ara[mid_indx]-এর ছোট হয়, তবে আমরা low_indx থেকে mid_indx – 1 সীমার মধ্যে খুঁজব। */  
         high_indx = mid_indx – 1;  
     }  
     else {  
         /* num যদি ara[mid_indx]-এর বড় হয়, তবে আমরা mid_indx + 1 থেকে high_indx সীমার মধ্যে খুঁজব। */  
         low_indx = mid_indx + 1;  
     }  
 }  
বাইনারি সার্চের প্রোগ্রাম আমরা লিখে ফেললাম। খুবই সহজ-সরল প্রোগ্রাম। সংখ্যাটি খুঁজে না পাওয়া পর্যন্ত লুপটি চলতেই থাকবে, কারণ আমরা লিখেছি while(1) আর 1 সব সময় সত্যি। কিন্তু সংখ্যাটি যদি ara-তে না থাকে তবে লুপটি চলতেই থাকবে এবং আমাদের প্রোগ্রাম কখনো বন্ধ হবে না। সুতরাং একটা ব্যবস্থা করা দরকার। আচ্ছা, আমরা কীভাবে বুঝব যে সংখ্যাটি ara-তে নেই? তোমরা ইতিমধ্যে লক্ষ করেছ যে আমরা প্রতিবার সার্চের সীমাটা অর্ধেক করে ফেলি। এভাবে চলতে থাকলে একসময় ওই সীমার ভেতর একটি সংখ্যাই থাকবে। তখন low এবং high-এর মান সমান হবে। আর প্রতিবার যেহেতু হয় low-এর মান বাড়ছে নাহয় high-এর মান কমছে, সুতরাং যেবার low আর high সমান হবে, তার পরের বার low-এর মান high-এর মানের চেয়ে বেশি হবে। তখন আমরা বুঝব যে সংখ্যাটি খুঁজে পাওয়া যায়নি। সুতরাং যতক্ষণ low <= high ততক্ষণ লুপটি চলবে। লুপ থেকে বের হয়ে যদি দেখি low > high, তখন বুঝব যে সংখ্যাটি খুঁজে পাওয়া যায়নি, আর না হলে বুঝব সংখ্যাটি খুঁজে পাওয়া গেছে এবং-এর মান ara[mid_indx]।

তাহলে পুরো প্রোগ্রামটি এবারে লিখে ফেলা যাক:
 #include <stdio.h>  
 int main()  
 {  
     int ara[] = {1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33 83, 87, 97, 99, 100};  
     int low_indx = 0;  
     int high_indx = 15;  
     int mid_indx;  
     int num = 97;  
     while (low_indx <= high_indx) {  
         mid_indx = (low_indx + high_indx) / 2;  
         if (num == ara[mid_indx]) {  
             break;  
         }  
         if (num < ara[mid_indx]) {  
             high_indx = mid_indx – 1;  
         }  
         else {  
             low_indx = mid_indx + 1;  
         }  
     }  
     if (low_indx > high_indx) {  
         printf("%d is not in the array\n", num);  
     }  
     else {  
         printf("%d is found in the array. It is the %d th element of the array.\n", ara[mid_indx], mid_indx);  
     }  
     return 0;  
 }  
 প্রোগ্রাম: ৮.১  
এবার তোমাদের কাজ হবে বাইনারি সার্চের জন্য একটি আলাদা ফাংশন লেখা।


আর বাইনারি সার্চ কীভাবে কাজ করে, সেটি এখানে সুন্দর করে অ্যানিমেশনের মাধ্যমে বোঝানো হয়েছে:
http://video.franklin.edu/Franklin/Math/170/common/mod01/binarySearchAlg.html

১৮টি মন্তব্য:

  1. আমি ৮.১ এর পুরো কোড টা কপি করে পেস্ট করলাম। কিন্তু কিছু এররর দেখাচ্ছে।
    line 4 error: expected '}' before numeric constant
    line 15 error: stray '\226' in program
    line 15 error: expected '}' before numeric constant

    উত্তরমুছুন
    উত্তরগুলি
    1. + কেটে + এবং - কেটে - আরেকবার লিখেন। কাজ হবে।

      মুছুন
  2. কপি পেস্ট করলে ঝামেলা আছে। নিজে নিজে টাইপ করলে হবে। :)

    উত্তরমুছুন
  3. বেয়াদবি মাফ করবেন দাদা , কিন্তু ”শুরুতে আমাদের তিনটি সংখ্যা জানতে হবে, সংখ্যাটির নিম্নসীমা (low), উচ্চসীমা (high) এবং সেই সংখ্যা (N)”….সংখ্যার নিম্ন সীমা – উচ্চ সীমা কি জিনিস বুঝলাম না :) :)

    উত্তরমুছুন
  4. আগের অংশটুকু পড়া থাকলে তো বোঝা উচিত, না বুঝলে অধ্যায়ের শুরু থেকে আবার পড়তে হবে। :)

    উত্তরমুছুন
  5. না মানে আমি বলতে চাইছিলাম , কথাটা “সংখ্যাটি যে ব্যবধির মধ্যে অবস্থিত সেই ব্যবধির নিম্ন সীমা - উচ্চ সীমা” হবে না ?? :) :)

    উত্তরমুছুন
  6. হ্যাঁ। তবে ব্যবধি শব্দটা আমি ব্যবহার করব না। তাহলে এটা গণিত পাঠ্যবইয়ের মত লাগবে। ব্যবধির ভদ্র কোনো প্রতিশব্দ থাকলে ব্যবহার করা যেত। তার চেয়ে নিম্নসীমা, উচ্চসীমা শব্দগুলোই ভালো। আমি কী বলতে চাচ্ছি সেটা পরিষ্কারভাবেই বোঝা যাচ্ছে ওখানে।

    উত্তরমুছুন
  7. function for 8.1 is not working. would you please tell me the reason...

    #include

    int binary_search(int ara[], int num, int low_indx, int high_indx, int mid_indx)
    {
    while (low_indx <= high_indx) {
    mid_indx = (low_indx + high_indx) / 2;
    if (num == ara[mid_indx]) {
    break;
    }
    if (num < ara[mid_indx]) {
    high_indx = mid_indx - 1;
    }
    else {
    low_indx = mid_indx + 1;
    }
    }
    }
    int main()

    {
    int ara[] = {1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33, 83, 87, 97, 99, 100};
    int low_indx = 0;
    int high_indx = 15;
    int mid_indx;
    int num = 97;
    mid_indx = binary_search(ara, num, low_indx, high_indx, mid_indx);
    if (low_indx > high_indx) {
    printf("%d is not in the array\n", num);
    }
    else {
    printf("%d is found in the array. It is the %d th element of the array.\n", ara[mid_indx], mid_indx);
    }
    return 0;
    }

    উত্তরমুছুন
  8. this time it's working but not quite properly. Please point out the mistake...

    #include

    int b_search(int ara[], int n, int low, int high, int mid)
    {
    while(1){
    (low < high);
    mid = (low + high) / 2;
    if(n == ara[mid]) {
    break;
    }
    if(n < ara[mid]) {
    high = mid - 1;
    }
    else if(n > ara[mid]) {
    low = mid + 1;
    }
    }
    if (low > high) {
    n != mid;
    }
    else {
    n = mid;
    }
    return;
    }

    int main()
    {
    int ara[] = {2, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33, 83, 87, 97, 99, 100};
    int n = 2;
    int low = 0;
    int high = 15;
    int mid;
    if (mid = b_search(ara, n, low, high, mid)) {
    printf("%d is found in the array. It is the %d th element of array.\n", ara[mid], mid + 1);
    }
    else {
    printf("%d is not in the array\n", n);
    }
    return 0;
    }

    উত্তরমুছুন
  9. পোস্টটি পড়ে ভাল লাগলো, আমি মনে করি বাংলাতে আপনি অনেক সুন্দর ভাবে বুঝিয়েছেন, ধন্যবাদ...

    উত্তরমুছুন
  10. The program don't run
    #include

    int main()
    {
    int a[]={1,2,5,4,7,8,9,6,2,11,25,45,87,88,90,91,92,95,97,100};
    int n=97;
    int m=0,h=19;
    int mid=(m+h)/2;
    while(m<=h){
    if (n==mid){
    break;
    }
    if (nh){
    printf("%d not found",n);
    }
    else{
    printf("%d is found,it is the %d th element of ara",a[mid],mid+1) ;
    }
    return 0;
    }

    Where is the mistake?Thank you.

    উত্তরমুছুন
  11. This program run
    #include

    int main()
    {
    int ara[] = {1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33 ,83, 87, 97, 99, 100};
    int low_indx = 0;
    int high_indx = 15;
    int mid_indx;
    int num = 97;
    while (low_indx <= high_indx)
    {
    mid_indx = (low_indx + high_indx) / 2;
    if (num == ara[mid_indx])
    {
    break;
    }
    if (num < ara[mid_indx])
    {
    high_indx = mid_indx - 1;
    }
    else
    {
    low_indx = mid_indx + 1;
    }
    }
    if (low_indx > high_indx) {
    printf("%d is not in the array\n", num);
    }
    else {
    printf("%d is found in the array. It is the %d th element of the array.\n", ara[mid_indx], mid_indx);
    }
    return 0;
    }

    উত্তরমুছুন
  12. বাইনারি সার্চ এর ফাংশান লিখলাম , আশা করি ঠিক আছে।
    ভুল হলে কেউ দয়া করে বলেন

    #include
    int binary_search(int ara[], int num, int low_index, int high_index)
    {
    int mid_index;
    while(low_index <= high_index)
    {
    mid_index = (low_index + high_index)/2;
    if(num == ara[mid_index])
    {
    break;
    }
    if(num < ara[mid_index])
    {
    high_index = mid_index -1;
    }
    else
    {
    low_index = mid_index + 1;
    }
    }

    return mid_index;
    }

    int main()
    {
    int ara[] = {1, 2, 5, 10, 20, 30, 35, 40, 45, 52, 62, 73, 84, 94, 97, 98};
    int low_index = 0;
    int high_index = 15;
    int num = 30;

    int mid_index = binary_search(ara, num, low_index, high_index);

    if(ara[mid_index] == num )
    {
    printf("%d is in array and positon is %d", ara[mid_index], mid_index + 1);
    }
    else
    {
    printf("%d is not in the array", num);
    }

    return 0;
    }

    উত্তরমুছুন
  13. সুবিন ভাই,
    বাইনারি সার্চ এর আরেকটি ফাংশান লিখলাম কেমন হল বলবেন দয়া করে?

    #include
    int binary_search(int num, int ara[], int low_index, int high_index)
    {
    int mid_index;
    while (low_index <= high_index)
    {
    mid_index = (low_index + high_index) / 2;
    if(num == ara[mid_index])
    {
    break;
    }
    if(num > ara[mid_index])
    {
    low_index = mid_index + 1;
    }
    else
    {
    high_index = mid_index -1;
    }
    }
    if(low_index > high_index)
    {
    return 0;
    }
    else
    {
    return mid_index;
    }
    }

    int main()
    {
    int ara[] ={1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33, 83, 87, 97, 100, 101};

    int num = 97;
    int low_index = 0;
    int high_index = 15;
    int search = binary_search(num, ara, low_index, high_index);
    if(search == 0)
    {
    printf("%d number is not in array", num);
    }
    else
    {
    printf("%d is in %d th position in array", num, search);
    }
    return 0;
    }

    উত্তরমুছুন
  14. mid_value=left+((right-left)/2)
    উপরের ফর্মুলাটি মিড ভ্যালু ফাইন্ড আউট করতে বেশ কিছু জায়গায় ব্যবহার করেছে।সেখানে এটিকে ওভারফ্লো যেনো না হয়,সেজন্যে ব্যবহার করেছে বলে বলতেছে।বিষয়টি ঠিক আমি ক্লিয়ার না,কারণ ওভারফ্লো হতে হলে এখানে একটি ভ্যালুকে নেগেটিভ হতে হবে।আমার প্রশ্ন হলো, লেনথ কি কখনো নেগেটিভ হতে পারে? হলেও গণণাটি কিভাবে হবে? অথবা আমার বুঝতে ভুল হলে স্যার একটু ক্লিয়ার করবেন আশা করি।

    উত্তরমুছুন
    উত্তরগুলি
    1. ধরা যাক, কেউ খুব বিশাল একটি অ্যারে ব্যবহার করছে বাইনারি সার্চের জন্য। এখন অ্যারেতে সার্চ করতে গিয়ে যদি এমন হয় যে left ও right-এর যোগফল ইন্টিজারের সর্বোচ্চ সীমা ছাড়িয়ে যায়, তখন ওভারফ্লো হবে। তাই সেই সম্ভাবনা এড়াতে mid_value = left + (right - left) / 2 ব্যবহার করা হয়, কারণ এখানে প্রথমে right - left করে সেটাকে 2 দিয়ে ভাগ করা হচ্ছে, তারপর left-এর সাথে যোগ করা হচ্ছে।

      Example: ধরা যাক, অ্যারের ইনডেক্স হচ্ছে ইন্টিজার যার সর্বোচ্চ মান হতে পারে 2147483647। এখন আমরা যদি একটি অ্যারেতে বাইনারি সার্চ করি, যেটিতে মোট 2140000003-টি সংখ্যা আছে, আর খুঁজতে খুঁজতে এমন পর্যায়ে আসি যেখানে left এর মান 2140000000, right-এর মান 2140000002, তখন left + right করলে তাদের যোগফল 2147483647-এর চেয়ে বড় হয়ে যাবে এবং ওভারফ্লো হয়ে সেটি একটি নেগেটিভ নাম্বার হয়ে যাবে। আর যদি right - left করি, তাহলে এর মান হয় 2। একে 2 দিয়ে ভাগ করলে ভাগফল 1। তারপরে একে আমরা left-র সাথে যোগ করলে যোগফল 2140000001। কোনো ওভারফ্লো হচ্ছে না। আশা করি বোঝাতে পেরেছি।

      মুছুন
  15. Perhaps, we can use long long int mid_value instead of using mid_value variable to avoid overflow. Am I right Subeen sir?

    উত্তরমুছুন

এখানে বিষয়সংশ্লিষ্ট মন্তব্য কিংবা প্রশ্ন করা যাবে। বাংলায় মন্তব্য করার সময় বাংলা হরফে লিখতে হবে। আর রোমান হরফে লিখলে ইংরেজিতে লিখতে হবে। নতুবা মন্তব্য প্রকাশ করা হবে না। ধন্যবাদ।