2.1 Basic Binary Search ও Counting Occurrences

চিনবেন কীভাবে

sorted array, "find efficiently", "first/last occurrence", "count of X in range"

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Find First and Last Position of Element — LC 34 (Medium — Google/Meta/Apple High)

Statement (Demo): sorted integer array nums ও integer target দেওয়া — target-এর starting ও ending position [first, last] হিসেবে return করুন। না থাকলে [-1, -1]। O(log n) time-এ করতে হবে। উদাহরণ: nums=[5,7,7,8,8,10], target=8 → [3,4] | ⚡ n ≤ 10⁵, -10⁹ ≤ nums[i] ≤ 10⁹

Approach: দুইবার binary search — একবার left-biased (match পেলে বামে চাপুন), একবার right-biased (match পেলে ডানে চাপুন)। এটাই "counting occurrences"-এরও ভিত্তি: last - first + 1।

function searchRange(nums, target) {
  const bound = (isFirst) => {
    let lo = 0,
      hi = nums.length - 1,
      ans = -1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] === target) {
        ans = mid;
        if (isFirst)
          hi = mid - 1; // আরও বামে খুঁজুন
        else lo = mid + 1; // আরও ডানে খুঁজুন
      } else if (nums[mid] < target) lo = mid + 1;
      else hi = mid - 1;
    }
    return ans;
  };
  return [bound(true), bound(false)];
}

Complexity: Time O(log n), Space O(1)

প্রবলেম

Search Insert Positionplan · দিন ০১২ LC 35
Statement: sorted unique integer array nums ও integer target দেওয়া — target থাকলে তার index, না থাকলে in-order insert করলে যে index হবে সেটা return করুন। O(log n) time।
উদাহরণ: nums=[1,3,5,6], target=5 → 2 | ⚡ n ≤ 10⁴, -10⁴ ≤ nums[i], target ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Binary Searchplan · দিন ০১১ LC 704
(টেমপ্লেট মুখস্থ লেখার প্র্যাকটিস)
Statement: ascending order-এ sorted integer array nums ও integer target দেওয়া — target-এর index return করুন। না থাকলে -1। O(log n) time।
উদাহরণ: nums=[-1,0,3,5,9,12], target=9 → 4 | ⚡ n ≤ 10⁴, -10⁴ ≤ nums[i], target ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Median of Two Sorted ArraysLC 4
(Hard — Google/Apple High; ছোট array-তে partition search)
Statement: দুটো sorted array nums1 (size m) ও nums2 (size n) দেওয়া — দুটো merge করলে যে sorted array হবে তার median বের করুন। O(log(m+n)) time।
উদাহরণ: nums1=[1,3], nums2=[2] → 2.0 | ⚡ m,n ≤ 1000, -10⁶ ≤ nums[i] ≤ 10⁶
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন