সার্চিং অ্যালগরিদম (Searching Algorithm)

লিনিয়ার সার্চ(Linear Search)

লিনিয়ার সার্চ সবচেয়ে ব্যাসিক সার্চ টেকনিক। ধরি আমাদের n টি নম্বর এর একটি অ্যাারে দেয়া আছে। এখন আরেকটি নম্বর a দিয়ে আমাকে জিজ্ঞাসা করা হল, এই a , আগের n টি নম্বর এর মাঝে আছে কিনা। স্বাভাবিকভাবে আমরা 0 থেকে n (অ্যাারে এর ঘর বিবেচনা করলে) পর্যন্ত একটি লুপ চালায়ে নম্বরটিকে বের করার চেষ্টা করবো।
int arr [ ] = { 1, 2, 4, 12, 14, 78, 21, -90, 111, 1467};
int a = 111;
for ( int i = 0; i < 10; i++ ){
          if ( arr [ i ] == a ){
                cout << " Found the number :D " << endl;
                break;
          }
}

সার্চিং এর ক্ষেত্রে লিনিয়ার সার্চ ছোট রেঞ্জ এর মধ্যে কাজ করবে কিন্তু রেঞ্জ বড় হয়ে গেলে TLE দিবে। আমরা লিনিয়ারি একটি পজিশন থেকে আরেকটি পজিশন এ যাচ্ছি ( n তম এলেমেন্ট পাওয়ার জন্য আমাদের শুরু থেকে n পর্যন্ত যেতে হবে), কাজেই লিনিয়ার সার্চের কমপ্লেক্সিটি O ( n )  [ Order of n ] যেখানে n হল কতটি এলেমেন্ট এর মাঝে সার্চিংটি চলছে।

বাইনারি সার্চ(Binary Search)

বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ টেকনিক এবং এর ব্যবহার ও খুব মজার। বাইনারি সার্চের জন্য প্রথমেই আমাদের নম্বরগুলিকে কোন একটি অর্ডার এ সাজাতে হবে ( Ascending or Descending )। এরপরে আমরা ২টি পজিশন সেট করবো low এবং high নামে। low  হবে আমাদের অ্যাারে এর 0th ইনডেক্স এবং high হবে (n-1)th ইনডেক্স। এখন আমরা এই high এবং low এর মাঝে থেকে middle ইনডেক্স বের করার চেষ্টা করবো এবং চেক করবো ঐ middle ইনডেক্স এর ভ্যালুটা আমাদের কাঙ্ক্ষিত ভ্যালুর সাথে মিলে গেছে কিনা। যদি মিলে যায়, তাহলে আমরা আমাদের ভ্যালু পেয়ে গেছি। যদি না মিলে, তবে ২টি কন্ডিশন হতে পারে।
১ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে বড়।
২ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে ছোট।
ধরি আমাদের অ্যাারেটি ছোট থেকে বড় আকারে সাজানো আছে। এখন ১ এর জন্য মিড ভ্যালুটি বড়, কাজেই আমাদের কাঙ্ক্ষিত ভ্যালুটি মিড ইনডেক্স এর অবশ্যই আগে আছে। কাজেই তখন আমাদের high হয়ে যাবে middle - 1 এবং low এর কোন চেঞ্জ হবেনা। ২ঃ এর খেত্রেও একই ব্যাপার। তখন low হবে middle + 1 এবং high এর কোন চেঞ্জ হবেনা। একটি উদাহরন দেখিঃ আমাদের ২০ কে খুঁজে বের করতে হবে।

টাইম কমপ্লেক্সিটি ঃ আমরা প্রতিবার সার্চিং এর জন্য একটি অংশ নিচ্ছি এবং অন্যটি বাদ দিয়ে দিচ্ছি। কাজেই worst case এর জন্য আমাদের কমপ্লেক্সিটি হবে O ( N * logN )।

স্যাম্পল কোড ঃ

	int binarySearch(int a[], int l, int r, int x) // recursive
	{
	if (r >= l)
	{
	int mid = l + (r - l)/2;
	// If the element is present at the middle itself
	if (a[mid] == x)
	return mid; // return the index
	// If element is smaller than mid, then
	// it can only be present in left subarray
	if (a[mid] > x)
	return binarySearch(a, l, mid-1, x);
	// Else the element can only be present
	// in right subarray
	return binarySearch(a, mid+1, r, x);
	}
	return -1;
	}

view raw binary search.cpp hosted with ❤ by GitHub

আমরা ভ্যালু পেয়ে গেলে ভ্যালুটির ইনডেক্স রিটার্ন করবো, আর না পেলে -1 রিটার্ন করবো। লক্ষ্য করলে দেখবে যে বাইনারি সার্চ এর টারমিনেট কন্ডিশন যখন high এর চেয়ে low এর ইনডেক্স বড় হয়ে যাবে। এই ব্যাপারগুলি ভালোভাবে খেয়াল না রাখলে ইনফিনিট লুপ এ পরবে প্রোগ্রাম। কোড করার সময় তাই আমাদের মাথায় রাখতে হবে আসলে কখন কোথায় কি হচ্ছে এবং কখন কোন কন্ডিশন দিলে ঠিকমতন প্রোগ্রাম রান করবে।