Java Technologies Binary Search এর ব্যবহার গাইড ও নোট

Binary Search হল একটি খুবই কার্যকরী অ্যালগরিদম যা sorted array বা sorted list তে একটি উপাদান দ্রুত খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি একটি divide and conquer অ্যালগরিদম, যা প্রতিটি পদক্ষেপে সম্ভাব্য সন্ধানকৃত উপাদানকে অর্ধেক করে ভাগ করে, ফলে এটি খুব দ্রুত কাজ করে।

এটি O(log n) সময় কমপ্লেক্সিটির সাথে কাজ করে, যা সাধারণ linear search এর O(n) টাইম কমপ্লেক্সিটির চেয়ে অনেক বেশি দ্রুত।

1. Binary Search Algorithm

Binary Search কাজ করে sorted array বা sorted list তে যেখানে গড় মান (middle element) এর সাথে তুলনা করে উপাদানটি খোঁজা হয়। এর মৌলিক পদক্ষেপ:

1. Middle Element: প্রথমে সোজা middle element নির্বাচন করা হয়।
2. Comparison: যদি middle element আপনার খুঁজে পাওয়া উপাদান হয়, তবে আপনি খুঁজে পেয়েছেন।
3. Left or Right Subarray: যদি middle element থেকে ছোট বা বড় মান খুঁজতে হয়, তবে আপনি array এর বাম বা ডান অংশে চলে যান এবং পুনরায় একই প্রক্রিয়া চালিয়ে যান।

2. Binary Search Algorithm Steps

1. Start with the full array and find the middle element.
2. If the middle element matches the target, return its index.
3. If the target is smaller than the middle element, repeat the search on the left half of the array.
4. If the target is larger than the middle element, repeat the search on the right half of the array.
5. If the element is not found, return a value indicating it’s not present (commonly -1).

3. Binary Search Example in Java

3.1. Recursive Binary Search Implementation

public class BinarySearch {

    // Recursive function to perform binary search
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // Element not found
        }

        int mid = left + (right - left) / 2;

        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found at mid
        }

        // If target is smaller than mid, search in the left subarray
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        }

        // If target is larger than mid, search in the right subarray
        return binarySearch(arr, mid + 1, right, target);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;

        int result = binarySearch(arr, 0, arr.length - 1, target);

        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

ব্যাখ্যা:

• binarySearch() ফাংশনটি রিকার্সিভভাবে left এবং right পয়েন্টার ব্যবহার করে মধ্যবর্তী উপাদান খুঁজে বের করে এবং তাকে টার্গেটের সাথে তুলনা করে।
• Base Case: যদি left > right হয়, তাহলে এটি দেখায় যে উপাদানটি খুঁজে পাওয়া যায়নি।
• Recursive Case: উপাদান পাওয়া না গেলে left বা right সাবঅ্যারে রিকার্সিভ কল করা হয়।

আউটপুট:

Element found at index: 3

3.2. Iterative Binary Search Implementation

public class BinarySearch {

    // Iterative function to perform binary search
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid; // Target found at mid
            }

            // If target is smaller than mid, search in the left subarray
            if (arr[mid] > target) {
                right = mid - 1;
            }
            // If target is larger than mid, search in the right subarray
            else {
                left = mid + 1;
            }
        }

        return -1; // Element not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;

        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

ব্যাখ্যা:

• Iterative Binary Search তে while লুপ ব্যবহার করা হয়েছে যেখানে left এবং right পয়েন্টার দ্বারা পুরো অ্যারে পার করে যাচ্ছি। যতক্ষণ না left পয়েন্টার right এর থেকে ছোট থাকে, ততক্ষণ লুপটি চলবে।
• এই পদ্ধতিতে রিকার্সন নেই, এবং এটি সাধারণত মেমরি ব্যবহারে সাশ্রয়ী।

আউটপুট:

Element found at index: 3

4. Time Complexity of Binary Search

• Time Complexity:
  • Best Case: O(1) (যখন প্রথমেই middle element হলো টার্গেট)
  • Worst Case: O(log n) (এটি প্রতি পদক্ষেপে ডাটা অর্ধেক করে কাটে)
  • Average Case: O(log n)
• Space Complexity:
  • Recursive Version: O(log n) (কারণ রিকার্সন কল স্ট্যাক)
  • Iterative Version: O(1) (কারণ লুপে কোনো অতিরিক্ত স্ট্যাকের প্রয়োজন হয় না)

5. Binary Search এর ব্যবহার

• Searching in Sorted Arrays: এটি sorted arrays বা sorted lists তে উপাদান খোঁজার জন্য ব্যবহৃত হয়।
• Efficient Search: একে দ্রুত searching এর জন্য ব্যবহৃত হতে পারে, যেখানে সাধারণ linear search অনেক ধীরে কাজ করে।
• Binary Search Tree (BST): এটি Binary Search Tree তে ব্যবহার হয় যেখানে প্রতিটি নোডের বাম দিকের মান ছোট এবং ডান দিকের মান বড় থাকে।

6. Binary Search with Matrix (2D array)

যখন আপনি 2D ম্যাট্রিক্সের মধ্যে বাইনারি সার্চ ব্যবহার করতে চান, তখন এটা সাধারণত row-wise বা column-wise সজ্জিত ম্যাট্রিক্সে কার্যকরী হয়। 2D ম্যাট্রিক্সের জন্য binary search বিভিন্ন কৌশল ব্যবহার করা যেতে পারে।

6.1. Binary Search in 2D Matrix Example

public class BinarySearch2D {
    public static boolean binarySearch2D(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        int left = 0, right = rows * cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / cols][mid % cols];

            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false; // Target not found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 60}
        };
        int target = 3;

        boolean result = binarySearch2D(matrix, target);
        System.out.println("Element found: " + result);
    }
}

আউটপুট:

Element found: true

সারাংশ

Binary Search হল একটি অত্যন্ত কার্যকরী এবং দ্রুত অ্যালগরিদম, যা sorted array বা sorted list তে O(log n) সময়ে কোনো উপাদান খুঁজে বের করে। Recursive এবং Iterative উভয় পদ্ধতিতে binary search ব্যবহার করা যেতে পারে এবং উভয় পদ্ধতিরই সুবিধা ও অসুবিধা রয়েছে। Binary Search বিভিন্ন ক্ষেত্র যেমন 2D matrix, binary search tree (BST) এবং sorted arrays তে ব্যবহৃত হয় এবং এটি efficient searching এর জন্য অপরিহার্য একটি টুল।