Binary Search-এ Lower Bound এবং Upper Bound কী?

Binary Search Algorithm-এর সবচেয়ে মজার বিষয় হলো এর Searching Mechanism।

Linear Search-এর মতো প্রতিটি Element একে একে Check না করে, Binary Search প্রতিবার Search Space-এর অর্ধেক বাদ দিয়ে দেয়। অর্থাৎ Target Value-এর তুলনায় যেসব Value নিশ্চিতভাবে বড় বা ছোট, সেগুলো আর কখনো Check করা হয় না। এর ফলেই Binary Search-এর Time Complexity হয় O(log n)।

এই Searching Mechanism থেকেই দুটি গুরুত্বপূর্ণ Concept এসেছে—

Lower Bound
Upper Bound

চলুন সহজ উদাহরণের মাধ্যমে বিষয় দুটি বুঝে নেওয়া যাক।

Lower Bound কী?

একটি Sorted Array-তে কোনো একটি Value-এর Lower Bound বলতে সেই Value-টিকেই বোঝায় যদি সেটি Array-তে উপস্থিত থাকে। আর যদি Value-টি উপস্থিত না থাকে, তাহলে তার থেকে ছোট সব Value-এর মধ্যে সবচেয়ে বড় (Maximum) Value-টিকে Lower Bound হিসেবে ধরা যায়।

ধরুন আমাদের একটি Sorted Array রয়েছে—

1, 2, 3, 4, 6, 8, 9, 10

এখন আমি যদি 5-এর Lower Bound বের করতে চাই—

5 Array-তে নেই।
5-এর থেকে ছোট Value গুলো হলো—

1, 2, 3, 4

এগুলোর মধ্যে সবচেয়ে বড় Value হলো—

অর্থাৎ,

Lower Bound(5) = 4

আর যদি 6-এর Lower Bound বের করি, তাহলে—

Lower Bound(6) = 6

কারণ Value-টি Array-তেই রয়েছে।

Note: প্রোগ্রামিং Language-এর Standard Library (যেমন C++ STL)-এ lower_bound() সাধারণত প্রথম এমন Element-এর Position Return করে যেটি Target-এর সমান বা বড় (≥ Target)। এই আর্টিকেলে Lower Bound-এর ব্যাখ্যাটি গাণিতিক ধারণা অনুযায়ী উপস্থাপন করা হয়েছে।

Upper Bound কী?

Upper Bound হলো Lower Bound-এর বিপরীত ধারণা।

একটি Sorted Array-তে কোনো একটি Value-এর Upper Bound বলতে সেই Value-টিকেই বোঝায় যদি সেটি উপস্থিত থাকে। আর যদি উপস্থিত না থাকে, তাহলে তার থেকে বড় সব Value-এর মধ্যে সবচেয়ে ছোট (Minimum) Value-টি Upper Bound হবে।

একই Array ব্যবহার করি—

1, 2, 3, 4, 6, 8, 9, 10

এখন আমি যদি 7-এর Upper Bound বের করতে চাই—

7 Array-তে নেই।
7-এর থেকে বড় Value গুলো হলো—

8, 9, 10

এগুলোর মধ্যে সবচেয়ে ছোট Value হলো—

অর্থাৎ,

Upper Bound(7) = 8

আর যদি 8-এর Upper Bound বের করি, তাহলে—

Upper Bound(8) = 8

কারণ Value-টি Array-তে উপস্থিত রয়েছে।

Note: C++ STL-এর upper_bound() Function সাধারণত Target-এর থেকে Strictly বড় (>) প্রথম Element-এর Position Return করে, যা এই গাণিতিক ব্যাখ্যা থেকে কিছুটা ভিন্ন।

উদাহরণ

ধরি আমাদের Sorted Array হলো—

1, 2, 3, 4, 6, 8, 9, 10

Target	Lower Bound	Upper Bound
3	3	3
5	4	6
6	6	6
7	6	8
10	10	10

Binary Search-এর সাথে এর সম্পর্ক

Binary Search শুধুমাত্র কোনো Value খুঁজে বের করার জন্যই ব্যবহৃত হয় না।

এই একই ধারণা ব্যবহার করে খুব দক্ষতার সাথে—

Lower Bound বের করা যায়।
Upper Bound বের করা যায়।
কোনো Value-এর Insert Position নির্ণয় করা যায়।
Frequency Count করা যায়।
Range Query Solve করা যায়।

এই কারণেই Competitive Programming এবং Data Structure & Algorithms (DSA)-এ Lower Bound এবং Upper Bound অত্যন্ত গুরুত্বপূর্ণ Concept।

উপসংহার

Binary Search-এর আসল শক্তি শুধু দ্রুত Search করার মধ্যে সীমাবদ্ধ নয়। এর Searching Mechanism থেকেই Lower Bound এবং Upper Bound-এর মতো শক্তিশালী Concept এসেছে, যা Sorted Data নিয়ে কাজ করার সময় বিভিন্ন সমস্যা খুব দক্ষতার সাথে সমাধান করতে সাহায্য করে।

তবে একটি বিষয় মনে রাখা গুরুত্বপূর্ণ—গাণিতিকভাবে Lower Bound এবং Upper Bound-এর ব্যাখ্যা এবং বিভিন্ন Programming Language-এর Standard Library (যেমন C++ STL)-এর lower_bound() ও upper_bound() Function-এর আচরণ এক নয়। তাই Interview, Competitive Programming বা Production Code-এ কাজ করার সময় কোন Definition ব্যবহার করা হচ্ছে, সেটি সবসময় নিশ্চিত হয়ে নেওয়া উচিত।