প্রোগ্রামিং বাইনারি সার্চ

প্রোগ্রামিং বাইনারি সার্চ

একটি সহজ খেলা দিয়ে শুরু করা যাক। এটি খেলতে দুজন দরকার। একজন মনে মনে একটি সংখ্যা ধরবে। আর দ্বিতীয়জন কিছু প্রশ্ন করে সেই সংখ্যাটি বের করবে। তবে 'তোমার সংখ্যাটি কত?' - এমন প্রশ্ন কিন্তু সরাসরি করা যাবে না। প্রশ্নটি হচ্ছে: সংখ্যাটি কি 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]।
তাহলে পুরো প্রোগ্রামটি এবারে লিখে ফেলা যাক: #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