🗓️ Day 14: Binary Search Variants

🧠 Concept Deep Dive

Binary Search can be adapted to solve more specific problems, like:

“Find the first occurrence of a value”
“Find the last occurrence of a value”
“Find the lower or upper bound for a target”

These are commonly needed in problems involving duplicate values or range conditions.

📖 Variant 1: First Occurrence

✨ Goal:

Return the index of the first occurrence of target in a sorted array.

function firstOccurrence(nums: number[], target: number): number {
  let low = 0, high = nums.length - 1;
  let result = -1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] === target) {
      result = mid;
      high = mid - 1; // Keep looking on the left
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

Example:

Input: nums = [1,2,4,4,4,5,6], target = 4
Output: 2  // First 4 is at index 2

📖 Variant 2: Last Occurrence

✨ Goal:

Return the index of the last occurrence of target in a sorted array.

function lastOccurrence(nums: number[], target: number): number {
  let low = 0, high = nums.length - 1;
  let result = -1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] === target) {
      result = mid;
      low = mid + 1; // Keep looking on the right
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

Example:

Input: nums = [1,2,4,4,4,5,6], target = 4
Output: 4  // Last 4 is at index 4

📖 Variant 3: Lower Bound

Same as Day 12, but recapped here:

✨ Goal:

Find the first index where element ≥ target.

function lowerBound(nums: number[], target: number): number {
  let low = 0, high = nums.length;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] < target) low = mid + 1;
    else high = mid;
  }
  return low;
}

Example:

Input: nums = [1,2,4,4,5,6], target = 4
Output: 2

📖 Variant 4: Upper Bound

✨ Goal:

Find the first index where element > target.

function upperBound(nums: number[], target: number): number {
  let low = 0, high = nums.length;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] <= target) low = mid + 1;
    else high = mid;
  }
  return low;
}

Example:

Input: nums = [1,2,4,4,5,6], target = 4
Output: 4

📊 Big O Complexity

Operation	Time	Space
Binary Search Variant	O(log n)	O(1)

🧪 Real-world Analogy

Imagine a line of people sorted by age. If you want to find the first person who is at least 18 years old or the last person who is exactly 21, these variants of binary search help you find those people efficiently!

🧪 LeetCode-style Homework

Problem: Find First and Last Position of Element in Sorted Array

function searchRange(nums: number[], target: number): number[] {
  const first = firstOccurrence(nums, target);
  const last = lastOccurrence(nums, target);
  return [first, last];
}

Note: Reuse the helper functions we wrote above.

Example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]

📆 Summary

First/Last occurrence and bounds are important extensions of binary search
All variants still run in O(log n)
Widely used in competitive coding and interviews

🔮 Up Next

▶️ Day 15: Binary Search on Answers