Lower and Upper Bound are specialized versions of Binary Search used to find specific boundaries in a sorted array containing duplicate elements.

Imagine a shelf of Books sorted by genre:

• ["Fantasy", "Horror", "Horror", "Horror", "Sci-Fi", "Sci-Fi"]

1. Lower Bound of "Horror": What is the first index where "Horror" starts? (Index 1).
2. Upper Bound of "Horror": What is the index after the last "Horror"? (Index 4, where "Sci-Fi" starts).
3. Range: If you subtract upper - lower, you get 3, which is the exact number of "Horror" books!

---

Lower Bound

The smallest index i such that nums[i] >= target.

• If the target exists, it's the index of the first occurrence.
• If the target doesn't exist, it's where the target should be inserted.

Upper Bound

The smallest index i such that nums[i] > target.

• It's ALWAYS the index after the last occurrence of the target.

---

javascript Standard
/**
 * Lower Bound - First index where nums[i] >= target
 */
function lowerBound(nums, target) {
  let low = 0;
  let high = nums.length; // Note: high is length, as target could be at the very end
  
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] >= target) {
      high = mid; // Narrow down to the left
    } else {
      low = mid + 1;
    }
  }
  return low;
}

/**
 * Upper Bound - First index where nums[i] > target
 */
function upperBound(nums, target) {
  let low = 0;
  let high = nums.length;
  
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] <= target) {
      low = mid + 1; // Narrow down to the right
    } else {
      high = mid;
    }
  }
  return low;
}

---

Top Techniques

• Find Total Occurrences: upperBound(arr, target) - lowerBound(arr, target).
• Search Insert Position: This is exactly what lowerBound does.
• Find First and Last Position of Element: [lowerBound, upperBound - 1].

Pro Tip

In some languages, these are built-in (e.g., std::lower_bound in C++). In JavaScript, you usually have to implement them yourself. Understanding the subtle difference between nums[mid] >= target and nums[mid] > target is the key to passing this interview question.