İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarTekrarlarHakkında
Dil
EnglishTürkçe

İkili Arama

Rehber 1 / 6 · Yol 1 / 6

ÖncekiSonraki →

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

Search in Rotated Sorted Array

Problem (yeniden ifade)

Benzersiz değerli sıralı bir dizi bilinmeyen bir pivotda döndürülmüş. nums ve target verildiğinde target’ın indeksini döndür; yoksa -1. O(log n) çalışmalı.

Sezgi

[lo,hi] aralığının en az bir yarısı sıralıdır. Hangi yarının sıralı olduğunu ve target’ın orada olup olmadığını kontrol et; diğer yarımı at.

Yaklaşımlar

Döndürülmüş dizide binary search

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

Fikir. lo≤hi iken mid hesapla. nums[mid]==target ise mid döndür. Sol yarı sıralıysa target aralıktaysa sola, değilse sağa ara; sağ yarı için simetrik.

Yürüyüş. [4,5,6,7,0,1,2], target=0 → mid sonunda pivot tarafına iner ve 0’ı bulur.

Trade-off. Sınırlarda ≤’ye dikkat. Yinelenenler (LC 81) farklı daraltma adımı ister.

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

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

Şablon bağlantısı

Hangi tarafın monoton olduğunu kontrol eden ek adımlı binary search.

Yansıma