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 Minimum in Rotated Sorted Array

Problem (yeniden ifade)

Benzersiz değerli sıralı bir dizi döndürülmüş. Minimum elemanı O(log n)’de bul.

Sezgi

Minimum, sıranın “kırıldığı” tek yerdir. Hangi yarının sıralı olduğuna karar vermek için mid’i sağ uçla karşılaştır.

Yaklaşımlar

Döndürmede binary search

Doğrulanmadı

Zaman O(log n)Alan O(1)

Fikir. nums[mid] > nums[hi] ise min sağda; değilse min mid’de veya solda.

Yürüyüş. [3,4,5,1,2] → mid=5 > 2 → sağda ara → min=1.

Trade-off. Doğrusal min taraması daha basit ama log-zaman şartını kaçırır.

Çözüm

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

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

Şablon bağlantısı

Döndürülmüş dizi binary search: minimum sırasız tarafta.

Yansıma

Minimum, döndürme kırılmasıdır. nums[mid] > nums[hi] ise min sağdadır. Neden lo tarafı değil?
Döndürülmemiş dizi: min nums[0]. Tek eleman.
Yinelenen yok; 154’te eşitlik neden ayrı dikkat ister?