Binary search: প্যাটার্ন, টেমপ্লেট ও সাধারণ ফাঁদ

Binary search sorted ক্রমে বারবার খোঁজার পরিসর অর্ধেক করে target খোঁজে। প্রতি ধাপে অর্ধেক বাদ যায়, তাই এটি O(log n)-এ চলে। দশ লাখ item-এ প্রায় ২০ ধাপ, দশ লাখ পর্যন্ত নয়।

ধারণা সহজ। বিস্তারিত ঠিক রাখা (সীমানা, off-by-one, অসীম loop) কঠিন অংশ, তাই একটি টেমপ্লেট শিখে তাতেই লেগে থাকুন।

ক্লাসিক রূপ

Sorted array-তে target-এর index খুঁজুন, না পেলে -1।

function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
// সময় O(log n), space O(1)

মূল বিষয়:

• [lo, hi] পরিসর অন্তর্ভুক্ত (inclusive) এবং ফাঁকা না হওয়া পর্যন্ত loop চলে (lo <= hi)।
• mid = lo + (hi - lo) / 2 নির্দিষ্ট আকারের integer-এর ভাষায় (Java, C++, Go) overflow এড়ায়। (lo + hi) / 2 overflow করতে পারে।
• সীমা সরানোর সময় mid বাদ দিন (mid + 1 বা mid - 1), কারণ ইতিমধ্যে দেখেছেন।

আরও কাজের রূপ: শর্ত প্রথম কোথায় সত্য হয় খুঁজুন

বেশিরভাগ ভিন্নতা আসলে এটাই: একটি হ্যাঁ/না শর্ত যেখানে মিথ্যা থেকে সত্যে বদলায় সেই সীমানা আছে, আর আপনি প্রথম সত্যটি চান। এই টেমপ্লেট lower bound, upper bound, প্রথম ও শেষ উপস্থিতি এবং "উত্তরের ওপর খোঁজা" সামলায়।

// [0, n)-এ প্রথম যে index-এ isTrue(index) সত্য তা ফেরত দেয়, না থাকলে n
function firstTrue(n, isTrue) {
  let lo = 0, hi = n;                 // half-open [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (isTrue(mid)) hi = mid;        // mid উত্তর হতে পারে, রাখুন
    else lo = mid + 1;                // mid মিথ্যা, বাদ দিন
  }
  return lo;
}

পরিসর half-open [lo, hi), আর hi = mid সম্ভাব্য উত্তর রাখে। এই রূপ সবসময় ছোট হয়, তাই অসীম loop হতে পারে না।

Lower bound ও upper bound

• Lower bound (প্রথম index যেখানে nums[i] >= target): isTrue = i => nums[i] >= target।
• Upper bound (প্রথম index যেখানে nums[i] > target): isTrue = i => nums[i] > target।
• Target-এর প্রথম উপস্থিতি: lower bound, তারপর মান মেলে কি না দেখুন।
• শেষ উপস্থিতি: upper bound বিয়োগ ১, তারপর যাচাই।
• Target-এর সংখ্যা: upper bound বিয়োগ lower bound।
• বসানোর অবস্থান: lower bound।

উত্তরের ওপর খোঁজা

Binary search শুধু array-তে নয়, যেকোনো একমুখী (monotonic) হ্যাঁ/না প্রশ্নে কাজ করে। "মান x কি যথেষ্ট?" জিজ্ঞেস করা যায় এবং x বাড়লে উত্তর একবারই বদলায়, তাহলে সরাসরি x খুঁজতে পারেন।

সমস্যা: সব স্তূপ h ঘণ্টায় শেষ করার ন্যূনতম খাওয়ার গতি (Koko Eating Bananas)।

function minSpeed(piles, h) {
  const canFinish = (speed) =>
    piles.reduce((hours, p) => hours + Math.ceil(p / speed), 0) <= h;
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canFinish(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}
// সময় O(n log M), M হলো বৃহত্তম স্তূপ

সাধারণ "উত্তরের ওপর খোঁজা" সমস্যা: সর্বোচ্চ ছোট করা (array ভাগ, D দিনে package পাঠানো), সর্বনিম্ন বড় করা (aggressive cows), বর্গমূল, ক্ষমতা ও হারের সমস্যা। ইঙ্গিত: "এমন ক্ষুদ্রতম/বৃহত্তম মান খুঁজুন যাতে কিছু সম্ভব হয়"।

Rotated sorted array

[4,5,6,7,0,1,2]-এর মতো array sorted ছিল তারপর ঘোরানো। যেকোনো mid-এ এক অর্ধেক সবসময় sorted। কোন অর্ধেক sorted ঠিক করুন, target তার ভেতরে কি না দেখুন, এবং অন্য অর্ধেক বাদ দিন।

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {                 // বাম অর্ধেক sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                     // ডান অর্ধেক sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

(ডুপ্লিকেট থাকলে সমস্যা কঠিন হয় এবং O(n)-এ নেমে যেতে পারে।)

সাধারণ ফাঁদ

• অসীম loop: ভুল mid রাউন্ডিং-সহ lo = mid বা hi = mid সরানো। একটি টেমপ্লেটে লেগে থাকুন।
• Off-by-one: inclusive hi = n - 1 ও half-open hi = n মেশানো। একটি ধরন বাছুন।
• নির্দিষ্ট আকারের integer-এর ভাষায় (lo + hi) / 2-এ overflow।
• Unsorted ইনপুট: binary search-এ sorted data (বা monotonic শর্ত) লাগে।
• ফাঁকা array ও একক-element ক্ষেত্র ভুলে যাওয়া।
• "উত্তরের ওপর খোঁজা"-য় ভুল সীমানা: আসল উত্তর [lo, hi]-এর মধ্যে আছে নিশ্চিত করুন।

অনুশীলনের সমস্যা

Binary Search, Search Insert Position, First and Last Position of Element, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Capacity to Ship Packages, Median of Two Sorted Arrays (কঠিন)।

মূল কথা: data sorted হলে বা হ্যাঁ/না শর্ত একবার বদলালে binary search ব্যবহার করুন। half-open পরিসরসহ "first true" টেমপ্লেট শিখুন, এবং মনে রাখুন এটি শুধু array-তে নয়, উত্তরেও কাজ করে।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ১ (মূল প্যাটার্ন): 4 নম্বর (মোট 5)। আগের লেখা: Two pointers ও sliding window: উদাহরণসহ প্যাটার্ন.