Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Binary Search

Guide 2 of 6 · Path 2 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search

Find First and Last Position of Element in Sorted Array

Problem (restated)

Find start and end indices of target in a sorted array, or [-1,-1]. O(log n).

Intuition

Two lower_bound searches for target and target+1.

Approaches

Lower & upper bound

Tested only
Time O(log n)Space O(1)

Idea. left = lower_bound(target); right = lower_bound(target+1)-1.

Walkthrough. [5,7,7,8,8,10], 8 → [3,4].

Trade-offs. Linear scan violates the log-time constraint.

Solution
export function searchRange(nums: number[], target: number): number[] {
  const lower = (t: number) => {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (nums[mid]! < t) lo = mid + 1; else hi = mid;
    }
    return lo;
  };
  const left = lower(target);
  if (left === nums.length || nums[left] !== target) return [-1, -1];
  return [left, lower(target + 1) - 1];
}

export function searchRange(nums: number[], target: number): number[] {
  const lower = (t: number) => {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (nums[mid]! < t) lo = mid + 1; else hi = mid;
    }
    return lo;
  };
  const left = lower(target);
  if (left === nums.length || nums[left] !== target) return [-1, -1];
  return [left, lower(target + 1) - 1];
}

Reflection