বাইনারি অনুসন্ধান একটি সাজানো অ্যারেতে কাজ করে। মানটি অ্যারের মধ্যম উপাদানের সাথে তুলনা করা হয়। যদি সমতা পাওয়া না যায়, তাহলে অর্ধেক অংশ বাদ দেওয়া হয় যেখানে মান নেই। একই ভাবে, বাকি অর্ধেক অংশ অনুসন্ধান করা হয়.
এখানে আমাদের অ্যারে মধ্য উপাদান. ধরা যাক আমাদের 62 খুঁজে বের করতে হবে, তারপর বাম অংশটি বাদ দেওয়া হবে এবং তারপর ডান অংশটি অনুসন্ধান করা হবে -
এগুলি হল একটি বাইনারি অনুসন্ধানের জটিলতা -
| সবচেয়ে খারাপ পারফরম্যান্স | O(log n) |
| বেস্ট-কেস পারফরম্যান্স | O(1) |
| গড় কর্মক্ষমতা | O(log n) |
| সবচেয়ে খারাপ স্পেস জটিলতা | O(1) |
উদাহরণ
আসুন বাইনারি সার্চ -
বাস্তবায়নের পদ্ধতি দেখিpublic static object BinarySearchDisplay(int[] arr, int key) {
int minNum = 0;
int maxNum = arr.Length - 1;
while (minNum <=maxNum) {
int mid = (minNum + maxNum) / 2;
if (key == arr[mid]) {
return ++mid;
} else if (key < arr[mid]) {
max = mid - 1;
}else {
min = mid + 1;
}
}
return "None";
} 