Searching Algorithms ডেটা স্ট্রাকচারের মধ্যে নির্দিষ্ট একটি উপাদান খোঁজার জন্য ব্যবহৃত হয়। Linear Search এবং Binary Search হল সাধারণত ব্যবহৃত দুটি অনুসন্ধান পদ্ধতি, তবে কিছু উন্নত অনুসন্ধান পদ্ধতিও রয়েছে, যেমন Jump Search, Interpolation Search, এবং Exponential Search। এই অ্যালগরিদমগুলি অনেক সময় বিশেষ ক্ষেত্রে অধিক কার্যকরী হতে পারে, যেমন সেগুলির ইনপুট ডেটা পূর্বে সাজানো থাকে বা নির্দিষ্ট ধরণের প্রোপার্টি থাকে।
এই টিউটোরিয়ালে, আমরা Jump Search, Interpolation Search, এবং Exponential Search অ্যালগরিদমগুলোর কার্যপ্রণালী এবং Java তে তাদের বাস্তবায়ন আলোচনা করব।
1. Jump Search
Jump Search হল একটি অনুসন্ধান অ্যালগরিদম যা একটি সাজানো অ্যারের মধ্যে দ্রুত অনুসন্ধান করার জন্য ব্যবহৃত হয়। এটি Block Search পদ্ধতির ওপর ভিত্তি করে কাজ করে, যেখানে অ্যারের মধ্যে একটি নির্দিষ্ট সাইজের "ঝাঁপ" (block) তৈরি করা হয়, তারপর ধীরে ধীরে এগিয়ে গিয়ে উপাদানটি খোঁজা হয়।
Steps:
- অ্যারের মধ্যে একটি বর্গমূল আকৃতির ব্লক নির্বাচন করা হয়।
- ব্লক ব্লক করে এগিয়ে যায় এবং একটি উপাদান পাওয়া গেলে, সেটি ডিটেইলসভাবে খোঁজা হয়।
উদাহরণ: Jump Search
public class JumpSearch {
public static int jumpSearch(int[] arr, int key) {
int n = arr.length;
int step = (int) Math.sqrt(n); // Calculate block size (step)
int prev = 0;
while (arr[Math.min(step, n) - 1] < key) {
prev = step;
step += (int) Math.sqrt(n);
if (prev >= n) {
return -1; // Key not found
}
}
// Linear search for key in block defined by prev and step
for (int i = prev; i < Math.min(step, n); i++) {
if (arr[i] == key) {
return i;
}
}
return -1; // Key not found
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};
int key = 15;
int index = jumpSearch(arr, key);
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}
ব্যাখ্যা:
- step: ব্লকের আকারটি sqrt(n) হিসাবে নির্ধারণ করা হয়।
- অ্যারের মধ্যে ধীরে ধীরে ব্লক অনুসন্ধান করা হয়, এরপর নির্দিষ্ট ব্লকে linear search ব্যবহার করে উপাদানটি খোঁজা হয়।
আউটপুট:
Element found at index: 7
2. Interpolation Search
Interpolation Search হল একটি উন্নত অনুসন্ধান অ্যালগরিদম যা সোজা অঙ্কন বা ইনপুট ডেটার মানের উপর ভিত্তি করে অ্যারের মধ্যে একটি উপাদান খোঁজে। এটি Binary Search এর মতো, তবে এটি পুরো অ্যারের মধ্য থেকে সম্ভাব্য অবস্থান নির্ধারণ করে এবং সঠিক অবস্থানে পৌঁছানোর জন্য এটি ইনপুট ডেটা মানের ওপর ভিত্তি করে অনুসন্ধান করে।
Steps:
- প্রথমে দুইটি সূচক (low এবং high) ব্যবহার করে, সেগুলির মধ্যে পরবর্তী সম্ভাব্য অবস্থান অনুমান করা হয়।
- এটি পরবর্তী অবস্থান থেকে অনুসন্ধান শুরু করে।
উদাহরণ: Interpolation Search
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int key) {
int low = 0, high = arr.length - 1;
while (low <= high && key >= arr[low] && key <= arr[high]) {
int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
// Check if key is found at pos
if (arr[pos] == key) {
return pos;
}
if (arr[pos] < key) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1; // Key not found
}
public static void main(String[] args) {
int[] arr = {10, 12, 18, 20, 35, 40, 45, 50, 55, 60};
int key = 35;
int index = interpolationSearch(arr, key);
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}
ব্যাখ্যা:
- Interpolation Formula:
pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])- এটি সম্ভাব্য অবস্থান গণনা করে।
- যদি key সরাসরি পাওয়া না যায়, তবে low এবং high সূচকগুলিকে সংশোধন করা হয়।
আউটপুট:
Element found at index: 4
3. Exponential Search
Exponential Search হল একটি অনুসন্ধান অ্যালগরিদম যা প্রথমে একটি বৃহত্তম পাওয়া এলিমেন্ট খোঁজার জন্য একটি এক্সপোনেনশিয়াল স্টেপের মাধ্যমে অ্যারের মধ্যে সরে যায় এবং পরে Binary Search ব্যবহার করে যথাযথ অবস্থান অনুসন্ধান করে।
Steps:
- প্রথমে এক্সপোনেনশিয়ালভাবে অবস্থান বাড়ানো হয়।
- একবারে যেটি পৌঁছানো হয়, সেখানে Binary Search ব্যবহার করা হয়।
উদাহরণ: Exponential Search
public class ExponentialSearch {
public static int exponentialSearch(int[] arr, int key) {
int n = arr.length;
if (arr[0] == key) {
return 0; // If the element is at index 0
}
int i = 1;
while (i < n && arr[i] <= key) {
i = i * 2; // Exponentially increase the index
}
return binarySearch(arr, key, i / 2, Math.min(i, n - 1)); // Perform binary search
}
private static int binarySearch(int[] arr, int key, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Key not found
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int key = 15;
int index = exponentialSearch(arr, key);
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}
ব্যাখ্যা:
- Exponential Search: প্রথমে এক্সপোনেনশিয়ালভাবে i বাড়ানো হয়, যতক্ষণ না উপাদানটি পাওয়া যায় বা খুঁজে বের করা হয়।
- একবার উপযুক্ত Binary Search সীমা চিহ্নিত হলে, সেখানেই Binary Search চালানো হয়।
আউটপুট:
Element found at index: 7
সারাংশ
এই তিনটি উন্নত অনুসন্ধান অ্যালগরিদম হল:
- Jump Search: এটি একটি সাজানো অ্যারের মধ্যে ব্লক ভিত্তিক অনুসন্ধান পদ্ধতি যা ব্লক ব্লক করে কাজ করে।
- Interpolation Search: এটি একটি উন্নত Binary Search যা ইনপুট ডেটার মানের উপর ভিত্তি করে অনুসন্ধান করে।
- Exponential Search: এটি এক্সপোনেনশিয়ালভাবে অবস্থান বাড়িয়ে পরে Binary Search ব্যবহার করে দ্রুত অনুসন্ধান করে।
এই অ্যালগরিদমগুলির মাধ্যমে একটি সাজানো অ্যারে থেকে উপাদান দ্রুত খুঁজে পাওয়া সম্ভব, বিশেষ করে যখন ডেটা নির্দিষ্ট প্যাটার্নে সাজানো থাকে।
Read more
