জাভাতে কীভাবে একটি বাইনারি অনুসন্ধান অ্যালগরিদম লিখবেন
কম্পিউটার মানুষের মতো জিনিসপত্র অনুসন্ধান করে না। যেখানে মানুষ কিছু খুঁজে বের করার জন্য তাদের দৃষ্টিভঙ্গি পরিবর্তন করতে পারে, কম্পিউটারকে একটি নির্দিষ্ট আইটেম কীভাবে সনাক্ত করতে হয় সে সম্পর্কে নির্দিষ্ট নির্দেশাবলী দেওয়া দরকার। সেখানেই স্ট্যান্ডার্ড অ্যালগরিদমগুলি কার্যকর।
বাইনারি অনুসন্ধান একটি আদর্শ অ্যালগরিদমের উদাহরণ। এগুলি আইটেমগুলির একটি সাজানো অ্যারেতে একটি উপাদান খুঁজে পেতে ব্যবহৃত হয়। এই গাইডে, আমরা বাইনারি অনুসন্ধানগুলি কী, সেগুলি কীভাবে কাজ করে এবং আপনি কীভাবে জাভাতে সেগুলি প্রয়োগ করতে পারেন সে সম্পর্কে কথা বলতে যাচ্ছি। আমরা একটি বাইনারি অনুসন্ধানের দুটি উদাহরণের মধ্য দিয়ে হেঁটে যাব:একটি পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে এবং অন্যটি পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে।
চলুন শুরু করা যাক!
একটি বাইনারি অনুসন্ধান কি?
একটি বাইনারি অনুসন্ধান একটি অনুসন্ধান অ্যালগরিদম যা একটি সাজানো অ্যারেতে একটি উপাদানের অবস্থান সনাক্ত করে।
একটি তালিকাকে অর্ধেক ভাগ করে বাইনারি অনুসন্ধান শুরু হয়। অনুসন্ধানটি তখন মধ্যবর্তী সংখ্যাটিকে সেই সংখ্যার সাথে তুলনা করবে যার জন্য অ্যালগরিদম অনুসন্ধান করছে৷
যদি সংখ্যাটি মধ্যম সংখ্যার চেয়ে ছোট হয়, এই প্রক্রিয়াটি তালিকার নীচের অর্ধেকের জন্য পুনরাবৃত্তি করা হয়; অন্যথায়, এই প্রক্রিয়াটি তালিকার উপরের অর্ধেকের জন্য পুনরাবৃত্তি করা হয়।
বাইনারি অনুসন্ধানগুলি রৈখিক অনুসন্ধানের চেয়ে বেশি দক্ষ, আরেকটি সাধারণ ধরণের অনুসন্ধান। এর কারণ হল অ্যালগরিদম যখনই একটি আইটেম খোঁজে, এটি দুটির একটি ফ্যাক্টর দ্বারা অনুসন্ধান করার জন্য আইটেমের সংখ্যা কমিয়ে দেয়।
বাইনারি অনুসন্ধানগুলি শুধুমাত্র আইটেমগুলির একটি সাজানো তালিকায় কার্যকর করা যেতে পারে। এর মানে হল যে আপনার যদি ইতিমধ্যে একটি সাজানো তালিকা না থাকে তবে বাইনারি অনুসন্ধান চালানোর আগে আপনাকে একটি সাজানোর অ্যালগরিদম ব্যবহার করে এটি সাজাতে হবে৷
81% অংশগ্রহণকারী বলেছেন যে তারা বুটক্যাম্পে যোগ দেওয়ার পরে তাদের প্রযুক্তিগত কাজের সম্ভাবনা সম্পর্কে আরও আত্মবিশ্বাসী বোধ করেছেন। আজই একটি বুটক্যাম্পের সাথে মিলিত হন৷
৷গড় বুটক্যাম্প গ্র্যাড একটি বুটক্যাম্প শুরু করা থেকে শুরু করে তাদের প্রথম চাকরি খোঁজা পর্যন্ত ক্যারিয়ারের পরিবর্তনে ছয় মাসেরও কম সময় ব্যয় করেছে।
বাইনারি অনুসন্ধান কিভাবে কাজ করে?
বাইনারি অনুসন্ধান দুটি উপায়ে প্রয়োগ করা যেতে পারে:পুনরাবৃত্তিমূলকভাবে বা পুনরাবৃত্তিমূলকভাবে।
একটি পুনরাবৃত্তিমূলক বাইনারি অনুসন্ধান হল এমন একটি যেখানে লুপগুলি একটি তালিকায় একটি আইটেম অনুসন্ধান করতে ব্যবহৃত হয়। একটি পুনরাবৃত্ত বাইনারি অনুসন্ধান একটি ফাংশন ব্যবহার করে যা একটি তালিকায় একটি আইটেম খুঁজে বার বার নিজেকে কল করে। পুনরাবৃত্ত বাইনারি অনুসন্ধান একটি আইটেম খুঁজে পেতে divide and conquer পদ্ধতি ব্যবহার করে।
আপনি আমাদের জাভা রিকারশন গাইডে রিকার্সন সম্পর্কে আরও জানতে পারেন।
একটি বাইনারি অনুসন্ধান বাস্তবায়নের জন্য সাধারণ অ্যালগরিদম আপনি যে পদ্ধতি ব্যবহার করার সিদ্ধান্ত নেন না কেন তা একই।
নিম্নলিখিত তালিকা বিবেচনা করুন:
| 6 | 7 | 8 | 9 | 10 |
আমরা আমাদের তালিকায় 7 নম্বরটি অনুসন্ধান করতে যাচ্ছি। শুরু করার জন্য, আমরা দুটি পয়েন্টার সেট করতে যাচ্ছি যা আমাদের তালিকার সর্বনিম্ন এবং সর্বোচ্চ অবস্থানের প্রতিনিধিত্ব করে:
| নিম্ন | | | | উচ্চ |
| 6 | 7 | 8 | 9 | 10 |
এর পরে, আমাদের অ্যারেতে মধ্যম উপাদানটি খুঁজে বের করতে হবে। আমরা সূত্রটি ব্যবহার করে এটি করতে পারি:(নিম্ন + উচ্চ) / 2। এই ক্ষেত্রে, মধ্যম উপাদানটি 8।
আমাদের অ্যালগরিদম তুলনা করবে যে মধ্যম উপাদানটি আমরা যেটির জন্য অনুসন্ধান করছি তার সমান কিনা। সংখ্যা সমান হলে আমাদের অনুসন্ধান বন্ধ হয়ে যেতে পারে। আমরা 7 নম্বর খুঁজছি, যা 8 এর সমান নয়, তাই আমাদের অনুসন্ধান চলতে থাকে।
আমাদের অ্যালগরিদম তুলনা করে যে সংখ্যাটির জন্য আমরা অনুসন্ধান করছি তা মধ্যম সংখ্যার চেয়ে বড় কিনা। যদি এটি বড় হয়, আমাদের অনুসন্ধান আমাদের তালিকার উপরের অর্ধেক থেকে আবার শুরু হবে। এটি নিম্ন সেট করার মাধ্যমে করা হয় নিম্ন =মধ্যম_সংখ্যা + 1 এর সমান। অন্যথায়, আমাদের তালিকার নীচের অর্ধেক থেকে অনুসন্ধান আবার শুরু হবে।
7 (আমরা যে সংখ্যাটি খুঁজছি) 8 (মাঝের সংখ্যা) এর বেশি নয়। এর মানে হল যে আমাদের অ্যালগরিদম আমাদের তালিকার নীচের অর্ধেক অনুসন্ধান করতে চলেছে। আমরা আমাদের "উচ্চ" মান উচ্চ =মধ্যম_সংখ্যা - 1 এ সেট করে এটি করি।
| নিম্ন | মধ্য | উচ্চ | | |
| 6 | 7 | 8 | 9 | 10 |
এখন, আমাদের অ্যালগরিদম আমাদের অনুসন্ধান পুনরাবৃত্তি করতে যাচ্ছে. আমরা মধ্যম সংখ্যা, 7 এর সাথে তুলনা করব যার জন্য আমরা অনুসন্ধান করছি। আমরা 7 নম্বর খুঁজছি, তাই আমাদের অনুসন্ধান অ্যালগরিদম বন্ধ হয়ে যায়। আমরা আমাদের তালিকায় 7 এর অবস্থান খুঁজে পেয়েছি!
কিভাবে একটি জাভা বাইনারি অনুসন্ধান বাস্তবায়ন করতে হয়
আমরা তত্ত্বের সাথে সম্পন্ন করেছি তাই এখন যা করা বাকি আছে তা হল আমাদের অনুসন্ধান বাস্তবায়ন। এটি একটি জিনিস যা আমরা নিজেরাই একটি তালিকা অনুসন্ধান করি; আমাদের জন্য অনুসন্ধান করে এমন একটি অ্যালগরিদম কোড করা সম্পূর্ণরূপে অন্য জিনিস।
আমরা একটি প্রোগ্রাম লিখে শুরু করব যা পুনরাবৃত্ত পদ্ধতি ব্যবহার করে একটি জাভা বাইনারি অনুসন্ধান প্রয়োগ করে।
পুনরাবৃত্ত পদ্ধতি
চলুন 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;
}
}
এই ফাংশনটি বাইনারি অনুসন্ধান ব্যবহার করে আমাদের আইটেমগুলির তালিকার মাধ্যমে অনুসন্ধান করে।
আমাদের ফাংশন চারটি প্যারামিটার গ্রহণ করে:যে তালিকার মাধ্যমে আমরা অনুসন্ধান করতে চাই (অ্যারে), যে আইটেমটির জন্য আমরা অনুসন্ধান করছি (অনুসন্ধানের জন্য), নিম্ন সংখ্যা (নিম্ন), এবং উচ্চ সংখ্যা (উচ্চ)।
আমাদের ফাংশনের ভিতরে আমরা একটি while লুপ ঘোষণা করেছি। যদিও "নিম্ন" এর মান "উচ্চ" এর থেকে কম বা সমান, লুপটি কার্যকর হবে।
আমাদের while লুপ মধ্যম সংখ্যা গণনা করে শুরু হয়। এটি তখন পরীক্ষা করে যে সেই অবস্থানের মানটি আমরা যেটির জন্য অনুসন্ধান করছি তার সমান কিনা।
যদি সেই সংখ্যাগুলি সমান হয়, সেই মানটি আমাদের প্রধান প্রোগ্রামে ফেরত দেওয়া হয়। যদি না হয়, আমাদের প্রোগ্রামটি পরীক্ষা করে যে মধ্যম অবস্থানের মানটি আমরা যেটির জন্য অনুসন্ধান করছি তার চেয়ে কম কিনা। যদি এটি হয়, একটি নতুন নিম্ন মান সেট করা হয়।
অন্যথায়, একটি নতুন উচ্চ মান সেট করা হয়েছে যাতে আমাদের তালিকা তালিকার উপরের অর্ধেকে আবার অনুসন্ধান করতে পারে।
যদি আমাদের আইটেম পাওয়া না যায়, -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. We've found the position of our number!
আমাদের প্রধান প্রোগ্রামটি বাইনারি সার্চ ক্লাসের একটি উদাহরণ শুরু করার মাধ্যমে শুরু হয়। আমরা প্রোগ্রামে আমাদের অনুসন্ধান latre শুরু করতে এটি ব্যবহার করি। তারপরে আমরা তিনটি ভেরিয়েবল সংজ্ঞায়িত করি:
- listToSearch:যে তালিকার মাধ্যমে আমরা অনুসন্ধান করতে চাই।
- লিস্টের দৈর্ঘ্য:তালিকার দৈর্ঘ্য।
- 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 ব্যবহার করি উচ্চ সংখ্যাটি নিম্ন সংখ্যার সমান বা কম কিনা তা পরীক্ষা করার জন্য বিবৃতি।
যদি এই বিবৃতিটি সত্য হয়, আমাদের অনুসন্ধান শুরু হয়। অন্যথায়, -1 ফেরত দেওয়া হয়, যা আমাদের প্রোগ্রামকে বলে যে একটি নির্দিষ্ট আইটেম তালিকায় পাওয়া যায়নি।
আমাদের if এর ভিতরে বিবৃতিতে, আমরা পরীক্ষা করি যে মাঝামাঝি সংখ্যাটির মান আমরা যেটির জন্য অনুসন্ধান করছি তার সমান কিনা। যদি তা হয়, আমরা সেই সংখ্যাটি আমাদের মূল প্রোগ্রামে ফেরত দিই।
যদি এই বিবৃতিটি সত্য হিসাবে মূল্যায়ন না করে, আমাদের প্রোগ্রামটি পরীক্ষা করে যে মধ্যম অবস্থানে থাকা সংখ্যাটি আমরা যেটির জন্য অনুসন্ধান করছি তার চেয়ে কম কিনা। যদি তা হয়, তাহলে searchItems() পদ্ধতিটি আবার চালানো হবে, তবে এবার আমাদের নিম্ন সংখ্যাটি আমাদের মধ্যম সংখ্যার চেয়ে এক বড়ের সমান হবে। এটি আমাদের তালিকার অনুসন্ধানের জন্য প্রয়োজনীয় আইটেমগুলির সংখ্যাকে দুই দ্বারা ভাগ করে।
অন্যথায়, searchItems() আবার চালানো হয় এবং সর্বোচ্চ সংখ্যার মান মাঝারি সংখ্যা বিয়োগ একের সমান করা হয়। এর মানে হল যে আমরা আমাদের অনুসন্ধান শুধুমাত্র আমাদের তালিকার বাম অর্ধেক পরিমার্জন করতে পারি।
আমরা আমাদের কোড পরীক্ষা করার জন্য আগে যে মেইন ফাংশনটি লিখেছিলাম সেটি ব্যবহার করতে পারি। আসুন দেখি আমরা আমাদের কোড চালালে কি হয়:
7 was found at index position 1.
আমাদের আইটেম আবার পাওয়া গেল! এইবার, আমরা একটি পুনরাবৃত্তিমূলক নম্বরের পরিবর্তে আমাদের নম্বর খোঁজার জন্য একটি পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করেছি৷
জটিলতা বিশ্লেষণ
বাইনারি অনুসন্ধান অ্যালগরিদমে O(1) এর একটি সেরা কেস জটিলতা রয়েছে। এটি ঘটে যখন অ্যালগরিদম দ্বারা তুলনা করা হয় এমন প্রথম আইটেমটি যা অনুসন্ধান করা হচ্ছে৷
একটি বাইনারি সার্চ অ্যালগরিদমে O(log n) এর গড় এবং সবচেয়ে খারাপ ক্ষেত্রে জটিলতা রয়েছে। এর মানে হল যে, বেশিরভাগ ক্ষেত্রে এবং সবচেয়ে খারাপ ক্ষেত্রে, অ্যালগরিদমের গতি লগারিদমিকভাবে ধীর হয়ে যায় তা নির্ভর করে তালিকাটি কতগুলি আইটেমের মাধ্যমে অনুসন্ধান করতে হবে তার উপর নির্ভর করে৷
উপসংহার
বাইনারি অনুসন্ধানগুলি একটি সাজানো তালিকায় একটি উপাদানের অবস্থান খুঁজে পেতে ব্যবহৃত হয়। বাইনারি অনুসন্ধানগুলি অ্যারের একটি অংশের মাঝখানে থাকা আইটেমটিকে সেই সংখ্যার সাথে তুলনা করে যার জন্য অ্যালগরিদম অনুসন্ধান করছে৷
বাইনারি অনুসন্ধানগুলি রৈখিক অনুসন্ধানের চেয়ে বেশি কার্যকর। এর কারণ হল যখনই একটি অনুসন্ধান করা হয় তখন যে মানগুলি অনুসন্ধান করা প্রয়োজন তার সংখ্যা দুটি দ্বারা ভাগ করা হয়।
এখন আপনি একজন বিশেষজ্ঞ প্রোগ্রামারের মতো জাভাতে একটি বাইনারি অনুসন্ধান বাস্তবায়নের জন্য প্রস্তুত৷
৷