বাইনারি অনুসন্ধান অ্যালগরিদম একটি বাছাই করা অ্যারেতে একটি নির্দিষ্ট মান খুঁজে বের করার জন্য একটি কার্যকর পদ্ধতি। এই পদ্ধতিটি অ্যারেটিকে ছোট অংশে বিভক্ত করে এবং সার্চ রেঞ্জের মাঝামাঝি অবস্থানে থাকা মানটিকে লক্ষ্য মানের সাথে তুলনা করে। মান মেলে, পছন্দসই মান পাওয়া যায়; অন্যথায়, অ্যালগরিদম অনুসন্ধানের পরিসরকে সংকুচিত করতে থাকে এবং মান পাওয়া না যাওয়া পর্যন্ত বা পরীক্ষা করার জন্য আর কোনো উপাদান অবশিষ্ট না থাকা পর্যন্ত প্রক্রিয়াটি পুনরাবৃত্তি করে।
ধাপ:
- অনুসন্ধান পরিসর শুরু করুন: প্রথম অবস্থান থেকে অ্যারের
leftশেষ অবস্থান পর্যন্ত অনুসন্ধান পরিসর নির্বাচন করে শুরু করুন।right - মধ্যবিন্দু খুঁজুন:
leftগড় এবং সঠিক অবস্থানের মাধ্যমে মধ্যবিন্দু গণনা করুন ; এটি অনুসন্ধান পরিসরের মধ্যবিন্দু। - মান তুলনা করুন: লক্ষ্য মানের সাথে মাঝের পয়েন্টে মান তুলনা করুন।
- তুলনা ফলাফল পরিচালনা করুন: যদি মধ্যবিন্দুর মান লক্ষ্য মানের সাথে মেলে তবে এই অবস্থানটি ফিরিয়ে দিন। যদি মধ্যবিন্দুতে মান লক্ষ্য মানের থেকে কম হয়, তাহলে ডান অর্ধেক অনুসন্ধান করতে বাম অবস্থানটি মধ্যম + 1-এ আপডেট করুন। যদি মধ্যবিন্দুতে মান লক্ষ্য মানের থেকে বেশি হয়, বাম অর্ধেক অনুসন্ধান করতে ডান অবস্থানটি মধ্যম- 1-এ আপডেট করুন।
- পুনরাবৃত্তি করুন: 2 থেকে 4 ধাপগুলি পুনরাবৃত্তি করুন যতক্ষণ না মান পাওয়া যায় বা চেক করার জন্য আর কোনো উপাদান নেই
left > right।
সুবিধাগুলি এবং অসুবিধাগুলি
সুবিধাদি:
- দক্ষ কর্মক্ষমতা: অ্যালগরিদমের সময় জটিলতা হল O(log n), এটিকে বড় ডেটাসেট পরিচালনার জন্য অত্যন্ত দক্ষ করে তোলে।
- বড় ডেটাসেটের জন্য কার্যকরী: বড় ডেটাসেটের জন্য দ্রুত পরীক্ষা করার জন্য উপাদানের সংখ্যা কমাতে বাইনারি অনুসন্ধান কার্যকর।
অসুবিধা:
- শুধুমাত্র সাজানো অ্যারেতে প্রযোজ্য: অ্যালগরিদম শুধুমাত্র সাজানো অ্যারেতে কাজ করে।
- ধাপের পরিবর্তনশীল সংখ্যা: মান খুঁজে বের করার জন্য প্রয়োজনীয় পদক্ষেপের সংখ্যা অ্যারেতে এর অবস্থানের উপর নির্ভর করে এবং এটি প্রান্তের কাছাকাছি মানগুলির জন্য অনেকগুলি পদক্ষেপ নিতে পারে।
উদাহরণ: পিএইচপি-তে সাজানো অ্যারেতে 12 মান খুঁজে বের করার জন্য বাইনারি অনুসন্ধান
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr)- 1;
while($left <= $right) {
$mid = floor(($left + $right) / 2);
if($arr[$mid] == $target) {
return $mid; // Return the position of the value
} elseif($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid- 1;
}
}
return -1; // Value not found
}
$array = [2, 5, 8, 12, 15, 20, 30];
$targetValue = 12;
$result = binarySearch($array, $targetValue);
if($result != -1) {
echo "Value $targetValue found at position $result.";
} else {
echo "Value $targetValue not found in the array.";
}
উদাহরণের ব্যাখ্যা
- আমরা প্রথম অবস্থান থেকে অ্যারের
left = 0শেষ অবস্থানে প্রাথমিক অনুসন্ধান পরিসর দিয়ে শুরু করি।right = 6 - আমরা বাম এবং ডান অবস্থানের গড় করে মধ্যবিন্দু(মাঝ) গণনা করি;
mid = 3. মাঝামাঝি মান হল 12। -
mid(12আমরা লক্ষ্য মান(12) এর সাথে) এর মান তুলনা করি এবং একটি মিল খুঁজে পাই, তাই আমরা অবস্থান 3 ফিরিয়ে দিই। - অ্যালগরিদম শেষ হয়, এবং আমরা ফলাফল আউটপুট করি "মান 12 অবস্থান 3 এ পাওয়া গেছে।"