মূল কনটেন্টে যান
🌍
গ্লোবাল DSA
প্যাটার্ন•টপিক 2 · Binary Search

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): Given a sorted integer array nums and a target, return its first and last positions as [first, last], or [-1, -1] if absent. Must run in O(log n). Example: nums=[5,7,7,8,8,10], target=8 → [3,4] | ⚡ n ≤ 10⁵, -10⁹ ≤ nums[i] ≤ 10⁹

Approach: Run binary search twice — once left-biased (on a match, keep going left), once right-biased (on a match, keep going right). This is also the basis of 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; // keep searching left
        else lo = mid + 1; // keep searching right
      } 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: Given a sorted array of unique integers nums and a target, return its index if found, otherwise the index where it would be inserted in order. O(log n).
    Example: nums=[1,3,5,6], target=5 → 2 | ⚡ n ≤ 10⁴, -10⁴ ≤ nums[i], target ≤ 10⁴

    নোট · ফাঁকা
  • Binary Searchplan · দিন ০৩২LC 704
    (practise writing the template from memory)

    Statement: Given an ascending sorted integer array nums and a target, return its index, or -1. O(log n).
    Example: nums=[-1,0,3,5,9,12], target=9 → 4 | ⚡ n ≤ 10⁴, -10⁴ ≤ nums[i], target ≤ 10⁴

    নোট · ফাঁকা
  • Median of Two Sorted Arraysplan · দিন ০৫১🔥 Must-doLC 4
    (Hard — Google/Apple High; partition search on the smaller array)

    Statement: Given sorted arrays nums1 (size m) and nums2 (size n), return the median of their merged order in O(log(m+n)).
    Example: nums1=[1,3], nums2=[2] → 2.0 | ⚡ m,n ≤ 1000, -10⁶ ≤ nums[i] ≤ 10⁶

    নোট · ফাঁকা