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

Easybinary-search

Search Insert Position

Problem (yeniden ifade)

Sıralı ve elemanları benzersiz bir dizide target’ın indeksini, yoksa sırayı bozmadan ekleneceği yeri döndür.

Sezgi

Klasik lower_bound: nums[i] ≥ target olan ilk indeks.

Yaklaşımlar

Lower bound binary search

Doğrulanmadı

Zaman O(log n)Alan O(1)

Fikir. lo/hi yarı-açık. mid < target ise lo=mid+1, değilse hi=mid. Cevap lo.

Yürüyüş. [1,3,5,6], target=5 → 2; target=2 → 1; target=7 → 4.

Trade-off. Lineer tarama O(n); binary search bu kalıbın alıştırması.

Çözüm

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

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

Şablon bağlantısı

Klasik lower_bound: nums[i] ≥ target olan ilk indeks.

Yansıma

“Yoksa ekleneceği yer” = alt sınır (bisect_left). Döngü bitince lo neden o indekstir?
target tüm elemanlardan küçük/büyük: 0 ve n.
lo + ((hi-lo)>>1) taşmayı neden önler?