İkili Arama

Nasıl düşünülür

Cevabı içermesi gereken aralığı koru. Ortayı sına; monoton teste göre yarısını at. Lower-bound formunu tercih et: lo = 0, hi = n (exclusive), lo == hi olana kadar daralt.

Şablon kontrol listesi

1. Arama uzayı nedir? (indeks, değer, cevap aralığı)
2. feasible(mid) ne demek?
3. İlk true mu son true mu istiyorsun?
4. Boş dizi ve tek eleman kenar durumlarını ele al.

Karmaşıklık temeli

O(log n) zaman, yinelemeli formda O(1) alan.

/** Binary search template: lower-bound, then exact match. */
export function binarySearch(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;
}

/** Binary search template: lower-bound, then exact match. */
export function binarySearch(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;
}