Easybinary-search

Binary Search

Problem (yeniden ifade)

Sıralı, birbirinden farklı tamsayı dizisi ve bir hedef verilir; hedefin indeksini veya -1 döndür.

Sezgi

Sıralı dizide klasik lower-bound ikili arama.

Yaklaşımlar

Lower-bound ikili arama

Verified

Time O(log n)Space O(1)

Fikir. lo=0, hi=n exclusive; while lo<hi mid=…; if nums[mid]<target lo=mid+1 else hi=mid. nums[lo] kontrol et.

Adım adım. nums=[-1,0,3,5,9,12], target=9 → indeks 4.

Trade-off’lar. Yinelemeli form özyineleme derinliği endişesini ortadan kaldırır.

Solution

export function search(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 < nums.length && nums[lo] === target ? lo : -1;
}

export function search(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 < nums.length && nums[lo] === target ? lo : -1;
}

Şablon bağlantısı

Binary Search şablonunun doğrudan uygulaması.

Yansıma

90 saniyede hangi kalıp bunu ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?