lthieu's notes

Pattern-Binary-Search

2 min read

Pattern — Binary Search

Khi nào dùng

Array sorted + tìm giá trị / vị trí. Hoặc bất kỳ “search space monotonic” nào.

Templates (3 dạng chuẩn)

1. Exact match

let lo = 0, hi = n - 1;
while (lo <= hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (nums[mid] === target) return mid;
  if (nums[mid] < target) lo = mid + 1;
  else hi = mid - 1;
}
return -1;

2. Lower bound (first index >= target)

let lo = 0, hi = n;       // hi = n, không phải n-1
while (lo < hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (nums[mid] < target) lo = mid + 1;
  else hi = mid;
}
return lo; // có thể = n nếu tất cả < target

3. Upper bound (first index > target)

while (lo < hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (nums[mid] <= target) lo = mid + 1;
  else hi = mid;
}
return lo;

Variants không phải sorted array

  • Rotated sorted (LC #33, #81, #153): xác định “half nào sorted”, search half đó.
  • Mountain array (LC #852, #162): tìm peak với invariant.
  • 2D matrix (LC #74, #240): treat as 1D với index conversion, hoặc staircase từ top-right.
  • Find First/Last Position (LC #34): chạy lower bound 2 lần.

Top problems

BàiLC
ClassicLC #704, #35
RotatedLC #33, #81, #153, #154
2DLC #74, #240
First/LastLC #34
PeakLC #162, #852

Pitfalls

  1. Off-by-one: lo <= hi (closed) vs lo < hi (half-open) — mỗi dạng có rule riêng cho lo = mid+1 / hi = mid / hi = mid-1. Chọn 1 dạng và stick với nó.
  2. Overflow mid: (lo+hi)/2 có thể overflow trong int32 — dùng lo + (hi-lo)/2.
  3. Infinite loop khi lo = mid (không +1): xảy ra khi lo và hi cách nhau 1 — phải dùng Math.ceil cho mid hoặc thay đổi invariant.
  4. Search space rỗng: kiểm tra if (n === 0) return -1 đầu hàm.

→ Nguồn lý thuyết: 05-Binary-Search · Variants nâng cao: Pattern-Binary-Search-on-Answer

Graph View

Backlinks