জাভা বাইনারি সার্চ: একটি সম্পূর্ণ গাইড

জাভা-তে বাইনারি সার্চ অ্যালগরিদম কীভাবে লিখবেন

কম্পিউটার মানুষের মতো আইটেম সার্চ করে না। মানুষ যেকোনো কিছু খুঁজতে তার পদ্ধতি পরিবর্তন করতে পারে, কিন্তু কম্পিউটারকে একটি নির্দিষ্ট আইটেম খুঁজে বের করার জন্য স্পেসিফিক ইনস্ট্রাকশন দিতে হয়। সেটিই স্ট্যান্ডার্ড অ্যালগরিদম কাজে লাগে।

বাইনারি সার্চ একটি স্ট্যান্ডার্ড অ্যালগরিদমের উদাহরণ। এটি সর্টেড অ্যারেতে একটি এলিমেন্টের অবস্থান খুঁজে বের করতে ব্যবহৃত হয়। এই গাইডে আমরা বাইনারি সার্চ কী, কীভাবে কাজ করে, এবং জাভা-তে কীভাবে ইমপ্লিমেন্ট করবেন তা আলোচনা করব। আমরা বাইনারি সার্চের দুটি উদাহরণ দেখব: একটি রিকার্সিভ পদ্ধতিতে, আরেকটি ইটারেটিভ পদ্ধতিতে।

চলুন শুরু করি!

বাইনারি সার্চ কী?

একটি বাইনারি সার্চ হলো একটি সার্চ অ্যালগরিদম যা একটি সর্টেড অ্যারেতে একটি এলিমেন্টের পজিশন খুঁজে বের করে।

বাইনারি সার্চ একটি তালিকাকে আধা ভাগ করে শুরু করে। সার্চটি তারপর মাঝপথের নম্বরটি সার্চ করছি সেই নম্বরটির সাথে তুলনা করে।

যদি নম্বরটি মাঝপথের নম্বর চেয়ে ছোট হয়, তবে এই প্রক্রিয়া তালিকার নিচের আধা অংশে পুনরাবৃত্তি হয়; অন্যথায়, তালিকার উপরের আধা অংশে।

বাইনারি সার্চ লিনিয়ার সার্চ (একটি অন্য সাধারণ সার্চ) চেয়ে বেশি দক্ষ। কারণ অ্যালগরিদম প্রতিবার আইটেম খুঁজতে গেলে সার্চ করার আইটেম সংখ্যা দ্বিগুণ হারে কমানো করে।

বাইনারি সার্চ শুধুমাত্র সর্টেড আইটেমের তালিকাতেই এক্সিকিউট করা যায়। অর্থাৎ, যদি আপনার কাছে ইতিমধ্যে একটি সর্টেড তালিকা না থাকে, তবে বাইনারি সার্চ চালানোর আগে আপনাকে একটি সর্টিং অ্যালগরিদম ব্যবহার করে সেটি সর্ট করতে হবে।

বাইনারি সার্চ কীভাবে কাজ করে?

বাইনারি সার্চ দুটি পদ্ধতিতে ইমপ্লিমেন্ট করা যায়: ইটারেটিভ বা রিকার্সিভ।

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

রিকার্শন সম্পর্কে আরও জানতে আমাদের জাভা রিকার্শন গাইড পড়তে পারেন।

বাইনারি সার্চ ইমপ্লিমেন্ট করার জেনারেল অ্যালগরিদম একই থাকে আপনি কোন পদ্ধতি বেছে নিলেও।

নিচের তালিকা বিবেচনা করুন:

আমরা আমাদের তালিকাতে ৭ নম্বরটি সার্চ করব। শুরুতে আমরা দুটি পয়েন্টার সেট করব যা আমাদের তালিকার সবচেয়ে নিম্ন এবং সর্বোচ্চ পজিশন রিপ্রেজেন্ট করবে:

এরপর আমাদের অ্যারেতে মাঝপথের এলিমেন্ট খুঁজে বের করতে হবে। এটি করতে পারি ফর্মুলা ব্যবহার করে: (low + high) / 2। এই কেসে মাঝপথের এলিমেন্ট হলো ৮।

আমাদের অ্যালগরিদম চেক করবে মাঝপথের এলিমেন্ট কি সার্চ করছি সেই নম্বরটির সমান। যদি সমান হয়, আমাদের সার্চ থামতে পারে। আমরা ৭ খুঁজছি, যা ৮ এর সমান নয়, তাই সার্চ চলবে।

আমাদের অ্যালগরিদম চেক করবে সার্চ করছি সেই নম্বরটি কি মাঝপথের নম্বর চেয়ে বড়। যদি বড় হয়, তবে আমাদের সার্চ আমাদের তালিকার উপরের আধা অংশে পুনরায় শুরু হবে। এটি করা হয় low কে middle_number + 1 এর সমান সেট করে। অন্যথায়, সার্চ তালিকার নিচের আধা অংশে শুরু হবে।

৭ (যেটি আমরা সার্চ করছি) ৮ (মাঝপথের নম্বর) চেয়ে বড় নয়। এর মানে আমাদের অ্যালগরিদম আমাদের তালিকার নিচের আধা অংশে সার্চ করবে। আমরা আমাদের "high" মানকে high = middle_number - 1 সেট করে এটি করব।

এখন, আমাদের অ্যালগরিদম আমাদের সার্চ পুনরাবৃত্তি করবে। আমরা মাঝপথের নম্বর, ৭, সার্চ করছি সেই নম্বরটির সাথে তুলনা করব। আমরা ৭ খুঁজছি, তাই আমাদের সার্চ অ্যালগরিদম থামবে। আমরা আমাদের তালিকাতে ৭-এর পজিশন খুঁজে পেলাম!

জাভা বাইনারি সার্চ ইমপ্লিমেন্ট করা

তেওরি শেষ, এখন বাকি হলো আমাদের সার্চ ইমপ্লিমেন্ট করা। নিজেরা তালিকা সার্চ করা এক回事; কিন্তু একটি অ্যালগরিদম কোড করা যা আমাদের জন্য সার্চ করবে তা সম্পূর্ণ অন্য একটি ব্যাপার।

আমরা ইটারেটিভ মেথড ব্যবহার করে জাভা বাইনারি সার্চ ইমপ্লিমেন্ট করার প্রোগ্রাম লিখতে শুরু করব।

ইটারেটিভ মেথড

searchItems নামে একটি ফাংশন ডিফাইন করি, যা আমাদের আইটেমের তালিকা সার্চ করবে:

class BinarySearch {
    int searchItems(int array[], int searchingFor, int low, int high) {
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (array[middle] == searchingFor) {
                return middle;
            } else if (array[middle] < searchingFor) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }
}

এই ফাংশন বাইনারি সার্চ ব্যবহার করে আমাদের আইটেমের তালিকা সার্চ করে।

আমাদের ফাংশন চারটি প্যারামিটার গ্রহণ করে: সার্চ করতে চাই সেই তালিকা (array), সার্চ করছি সেই আইটেম (searchingFor), নিম্ন নম্বর (low), এবং সর্বোচ্চ নম্বর (high)।

আমাদের ফাংশনের ভেতরে আমরা একটি while লুপ ঘোষণা করেছি। "low" এর মান "high" এর চেয়ে কম বা সমান থাকতে থাকবে, লুপ এক্সিকিউট হবে।

আমাদের while লুপ মাঝপথের নম্বর ক্যালকুলেট করে শুরু করে। তারপর চেক করে সেটি পজিশনের মান কি সার্চ করছি সেই নম্বরটির সমান।

যদি সমান হয়, সেটি আমাদের মেইন প্রোগ্রামে ফেরত দেয়া হয়। যদি না হয়, আমাদের প্রোগ্রাম চেক করে মাঝপথের পজিশনের মান কি সার্চ করছি সেই নম্বর চেয়ে কম। যদি কম হয়, একটি নতুন low মান সেট হয়।

অন্যথায়, একটি নতুন high মান সেট হয় যাতে আমাদের তালিকা আপার হাফে আবার সার্চ করতে পারে।

আমাদের আইটেম খুঁজে না পেলে, -1 ফেরত দেওয়া হয়। আমরা একটু পরে আমাদের মেইন প্রোগ্রামকে বলব যে তালিকায় আইটেমটি খুঁজে পাওয়া যায়নি।

আমাদের কোড এখনো কিছু করছে না কারণ আমরা আমাদের মেইন প্রোগ্রাম লিখিনি। searchItems() ফাংশনের নিচে আপনার BinarySearch ক্লাসে নিচের কোড যোগ করুন:

public static void main(String args[]) {
    BinarySearch newSearch = new BinarySearch();
    int listToSearch[] = { 6, 7, 8, 9, 10 };
    int listLength = listToSearch.length;
    int numberToFind = 7;
    int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1);
    if (findNumber != -1) {
        System.out.println(numberToFind + " was found at index position " + findNumber + ".");
    } else {
        System.out.println(numberToFind + " was not found in the list.");
    }
}

কোড চালালে:

7 was found at index position 1.

আমাদের মেইন প্রোগ্রাম BinarySearch ক্লাসের একটি ইনস্ট্যান্স আরম্ভ করে শুরু করে। আমরা এটি পরে আমাদের সার্চ শুরু করতে ব্যবহার করব। তারপর আমরা তিনটি ভেরিয়েবল ডিফাইন করি:

• listToSearch: যে তালিকায় আমরা সার্চ করতে চাই।
• listLength: তালিকার দৈর্ঘ্য।
• numberToFind: তালিকায় আমরা যে নম্বরটি খুঁজছি।

এই ভেরিয়েবলগুলো ডিফাইন হয়ে গেলে, আমরা আগে ঘোষণা করা searchItems() ফাংশন ব্যবহার করে আমাদের তালিকায় একটি নম্বর খুঁজে বের করি। এই ফাংশন যা ফেরত দেয় সেটি আমরা "findNumber" ভেরিয়েবলে অ্যাসাইন করি।

যদি findNumber -1 এর সমান না হয় (মানে আমাদের নম্বরটি খুঁজে পাওয়া গেছে), তবে সার্চ করছি সেই আইটেমের ইনডেক্স পজিশন কনসোলে প্রিন্ট করা হয়। অন্যথায়, কনসোলে একটি মেসেজ প্রিন্ট করা হয় যে নম্বরটি তালিকায় পাওয়া যায়নি।

রিকার্সিভ মেথড

বাইনারি সার্চ ইমপ্লিমেন্ট করার জন্য একটি রিকার্সিভ পদ্ধতি নেওয়া যায়। এখানে আপনি একটি ফাংশন লিখবেন যা নিজে থেকে নিজেকে কল করবে যতক্ষণ না নির্দিষ্ট আইটেমটি খুঁজে পায়।

রিকার্সিভভাবে আমাদের বাইনারি সার্চ পারফর্ম করার ফাংশন ডিফাইন করি:

class BinarySearch {
    int searchItems(int array[], int searchingFor, int low, int high) {
        if (high >= low) {
            int middle = low + (high - low) / 2;
            if (array[middle] == searchingFor) {
                return middle;
            } else if (array[middle] < searchingFor) {
                searchItems(array, searchingFor, middle + 1, high);
            } else {
                searchItems(array, searchingFor, low, middle - 1);
            }
        }
        return -1;
    }
}

এই ফাংশন আমাদের বাইনারি সার্চ ভিন্নভাবে ইমপ্লিমেন্ট করে। while লুপের বদলে, আমরা একটি if স্টেটমেন্ট ব্যবহার করি চেক করার জন্য high নম্বর কি low নম্বরের সমান বা কম।

যদি এই স্টেটমেন্ট true হয়, আমাদের সার্চ শুরু হয়। অন্যথায়, -1 ফেরত দেওয়া হয়, যা আমাদের প্রোগ্রামকে বলে নির্দিষ্ট আইটেমটি তালিকায় পাওয়া যায়নি।

আমাদের if স্টেটমেন্টের ভেতরে, আমরা চেক করি মাঝপথের নম্বরের মান কি সার্চ করছি সেই নম্বরটির সমান। যদি হয়, আমরা সেটি আমাদের মেইন প্রোগ্রামে ফেরত দেই।

যদি এই স্টেটমেন্ট true না হয়, আমাদের প্রোগ্রাম চেক করে মাঝপথের পজিশনের নম্বর কি সার্চ করছি সেই নম্বর চেয়ে কম। যদি কম হয়, searchItems() মেথড আবার চালবে, কিন্তু এইবার আমাদের low নম্বর আমাদের মাঝপথের নম্বর থেকে এক বড় হবে। এতে আমাদের তালিকার সার্চ করতে হয় সেই আইটেম সংখ্যা দ্বিগুণ হারে কমে যাবে।

অন্যথায়, searchItems() আবার চালবে এবং সর্বোচ্চ নম্বরের মান মাঝপথের নম্বর থেকে এক কম করা হবে। এর মানে আমরা আমাদের সার্চ শুধু তালিকার বাম আধা অংশে সীমাবদ্ধ করতে পারব।

আমরা আগে লিখা একই মেইন ফাংশন ব্যবহার করে আমাদের কোড টেস্ট করতে পারি। কোড চালালে:

7 was found at index position 1.

আমাদের আইটেম আবার খুঁজে পাওয়া গেল! এইবার, আমরা ইটারেটিভ পদ্ধতির বদলে রিকার্সিভ পদ্ধতি ব্যবহার করেছি।

কমপ্লেক্সিটি অ্যানালিসিস

বাইনারি সার্চ অ্যালগরিদমের 베スト কেস কমপ্লেক্সিটি O(1)। এটি তখন হয় যখন অ্যালগরিদম প্রথমে তুলনা করে সেই আইটেমটি পায় যা সার্চ করা হচ্ছে।

বাইনারি সার্চ অ্যালগরিদমের এভারেজ এবং ওৰ্স্ট কেস কমপ্লেক্সিটি O(log n)। এর মানে, অধিকাংশ কেসে এবং ওৰ্স্ট কেসে, অ্যালগরিদমের গতি লগারিদমিকভাবে ধীর হয় তালিকায় কতগুলো আইটেম সার্চ করতে হবে সেটির ওপর নির্ভর করে।

উপসংহার

বাইনারি সার্চ একটি সর্টেড তালিকায় একটি এলিমেন্টের পজিশন খুঁজে বের করতে ব্যবহৃত হয়। বাইনারি সার্চ একটি অ্যারের একটি অংশের মাঝপথের আইটেমকে সার্চ করছি সেই নম্বরটির সাথে তুলনা করে।

বাইনারি সার্চ লিনিয়ার সার্চ চেয়ে বেশি দক্ষ। কারণ প্রতিবার সার্চ পারফর্ম হলে সার্চ করার ভ্যালু সংখ্যা দ্বিগুণ হারে কমে যায়।

এখন আপনি জাভা-তে বাইনারি সার্চ এক্সপার্ট প্রোগ্রামারের মতো ইমপ্লিমেন্ট করতে পারবেন।