Search (অনুসন্ধান) হলো একটি গুরুত্বপূর্ণ অ্যালগরিদম, যা কোনো তালিকা বা অ্যারে থেকে নির্দিষ্ট উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। অনুসন্ধান দুই ধরনের হয়ে থাকে: Linear Search এবং Binary Search। এগুলোর মধ্যে পার্থক্য হল যে Linear Search কোন ধরনের সাজানো অ্যারেতে কাজ করতে পারে, যেখানে Binary Search শুধুমাত্র সাজানো অ্যারেতেই কার্যকরী।
Linear Search
Linear Search (লিনিয়ার সার্চ) একটি সাধারণ এবং সহজ পদ্ধতি যা একটি অ্যারে বা তালিকার প্রতিটি উপাদান একে একে পরীক্ষা করে যতক্ষণ না তা নির্দিষ্ট উপাদানটির সাথে মেলে। এটি একটি O(n) অ্যালগরিদম, যেখানে n হল অ্যারের আকার। অর্থাৎ, অ্যারের প্রতিটি উপাদানকে একবার করে পরীক্ষা করতে হয়।
বৈশিষ্ট্য:
- সহজ এবং সরল
- অ্যারে সাজানো কিনা তা কোনো বিষয় নয়
- খারাপ ক্ষেত্রে O(n) সময় জটিলতা
উদাহরণ:
public class LinearSearch {
// Linear Search function
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Return the index if found
}
}
return -1; // Return -1 if target is not found
}
public static void main(String[] args) {
int[] arr = {12, 45, 23, 8, 34, 67};
int target = 23;
int result = linearSearch(arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index: " + result);
}
}
}
আউটপুট:
Element found at index: 2
এখানে, linearSearch() ফাংশনটি অ্যারের প্রতিটি উপাদান পরীক্ষা করে দেখছে যে কোনো উপাদান target এর সমান কিনা। যদি সমান হয়, তাহলে তার ইনডেক্স রিটার্ন করে, না হলে -1 রিটার্ন করে।
Binary Search
Binary Search (বাইনারি সার্চ) একটি দ্রুত অনুসন্ধান পদ্ধতি যা শুধুমাত্র সাজানো অ্যারেতে কাজ করে। এটি প্রতি ধাপে অ্যারেকে অর্ধেক করে বিভক্ত করে, যেখানে মাঝের উপাদানটি লক্ষ্য উপাদানটির চেয়ে বড় না ছোট তা পরীক্ষা করে। এটি O(log n) সময় জটিলতা প্রদান করে, কারণ প্রতি ধাপে এটি অনুসন্ধান পরিসরকে অর্ধেক করে দেয়।
বৈশিষ্ট্য:
- শুধুমাত্র সাজানো অ্যারেতে কাজ করে
- দ্রুত, কারণ এটি প্রতিটি ধাপে অনুসন্ধান পরিসরকে অর্ধেক করে
- খারাপ ক্ষেত্রে O(log n) সময় জটিলতা
উদাহরণ:
public class BinarySearch {
// Binary Search function
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; // To prevent overflow
// Check if target is present at mid
if (arr[mid] == target) {
return mid;
}
// If target is smaller, ignore right half
if (arr[mid] > target) {
right = mid - 1;
}
// If target is larger, ignore left half
else {
left = mid + 1;
}
}
return -1; // Return -1 if target is not found
}
public static void main(String[] args) {
int[] arr = {2, 8, 12, 23, 34, 45, 67};
int target = 23;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index: " + result);
}
}
}
আউটপুট:
Element found at index: 3
এখানে, binarySearch() ফাংশনটি প্রথমে অ্যারের মাঝের উপাদান পরীক্ষা করে, তারপর যদি লক্ষ্য উপাদান তার চেয়ে ছোট হয় তবে ডান দিকে এবং বড় হলে বাম দিকে অনুসন্ধান করতে থাকে। এটি শুধুমাত্র সাজানো অ্যারেতে কাজ করে।
সারাংশ
- Linear Search (লিনিয়ার সার্চ) একটি সহজ এবং সরল পদ্ধতি যা অ্যারের প্রতিটি উপাদানকে একে একে পরীক্ষা করে। এটি সাধারণত ছোট ডেটা সেটে ব্যবহার করা হয় এবং সময় জটিলতা O(n)।
- Binary Search (বাইনারি সার্চ) একটি দ্রুত পদ্ধতি যা শুধুমাত্র সাজানো অ্যারেতে কাজ করে এবং প্রতি ধাপে অনুসন্ধান পরিসরকে অর্ধেক করে দেয়, ফলে সময় জটিলতা O(log n) থাকে।
এই দুটি অ্যালগরিদমের মধ্যে, Binary Search বড় ডেটা সেটে অনেক বেশি কার্যকরী, তবে এটি শুধুমাত্র সাজানো অ্যারেতেই কাজ করে, যেখানে Linear Search যে কোনো অ্যারে বা তালিকার জন্য উপযুক্ত, তবে তা অপেক্ষাকৃত ধীর গতির।
Read more
