Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumbinary-search

Find First and Last Position of Element in Sorted Array

Problem (yeniden ifade)

Sıralı bir dizide target’ın başlangıç ve bitiş indekslerini bul; yoksa [-1,-1]. O(log n).

Sezgi

target ve target+1 için iki lower_bound araması.

Yaklaşımlar

Lower ve upper bound

Doğrulanmadı

Zaman O(log n)Alan O(1)

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

Yürüyüş. [5,7,7,8,8,10], 8 → [3,4].

Trade-off. Doğrusal tarama log-zaman kısıtını bozar.

Çözüm

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];
}

Şablon bağlantısı

Binary-search şablonundan iki lower_bound (target ve target+1).

Yansıma

Aynı target için sol sınır ve sağ sınır iki ayrı ikili arama. hi = mid vs lo = mid+1 farkı nedir?
Yoksa [-1,-1]. İlk isabeti bulup lineer genişletmek O(n)’e kaçabilir — neden yasak?
target dizinin en solunda / en sağında: mid taşması var mı?