Searching &
Binary Search

8.1 Linear Search — quét tuyến tính

Đơn giản nhất: duyệt từ đầu đến cuối, so sánh từng phần tử.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

• Time: O(n) — worst case
• Best case: O(1) — phần tử đầu
• Space: O(1)
• Yêu cầu: không cần mảng sort

Khi nào Linear Search là đủ tốt?

• n nhỏ (ít hơn vài trăm)
• Mảng chưa sort và không có lookup nhiều lần
• Search phức tạp (so sánh nhiều điều kiện) — sort tốn hơn

JS có sẵn: arr.indexOf(target), arr.includes(target), arr.find(predicate) — đều O(n).

8.2 Binary Search cơ bản — O(log n)

Yêu cầu: mảng đã sort. Mỗi bước, so sánh phần tử giữa với target → loại nửa không chứa target. Sau k bước, không gian tìm kiếm giảm từ n xuống n/2^k. Tới k = log₂ n thì còn 1 phần tử.

Template chuẩn — học thuộc

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);  // tránh overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target)   lo = mid + 1;
    else                     hi = mid - 1;
  }
  return -1;
}

3 chú ý quan trọng

1. Tính mid an toàn: lo + Math.floor((hi - lo) / 2) thay vì (lo + hi) / 2. Trong các ngôn ngữ có integer overflow (Java/C++), lo + hi có thể tràn 32-bit khi cả hai gần INT_MAX. JS không có vấn đề này nhưng vẫn nên viết quen tay.
2. Điều kiện vòng lặp: lo <= hi (có dấu bằng) khi tìm chính xác. Nếu là lo < hi thì có khi không kiểm tra cuối cùng.
3. Cập nhật: mid + 1 hoặc mid - 1. Nếu chỉ đặt lo = mid, vòng lặp có thể không tiến → infinite loop.

Visualizer: tìm 17 trong [3,7,9,11,14,15,16,17]

Bước 1: lo=0, hi=7, mid=3 → arr[3]=11... đợi đã, mid của 0..7 là (0+7)/2 = 3.5 → 3. arr[3]=11 < 17 → lo = 4.

Bước 2: lo=4, hi=7, mid=5 → arr[5]=15 < 17 → lo = 6.

Bước 3: lo=6, hi=7, mid=6 → arr[6]=16 < 17 → lo = 7.

Bước 4: lo=7, hi=7, mid=7 → arr[7]=17 = target → return 7. Tổng 4 bước (≈ log₂ 8 = 3 + 1 cho việc kiểm tra cuối).

8.3 Bugs off-by-one nổi tiếng — kẻ thù của binary search

Bug 1: Vòng lặp vô hạn khi lo = mid

// ❌ SAI — vòng lặp vô hạn khi lo == hi-1
function buggy(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < target) lo = mid;       // ← không phải mid+1
    else hi = mid;
  }
  // ...
}
// Khi lo=2, hi=3 → mid=2 → nếu arr[2]<target thì lo=2 (không đổi!) → infinite loop

Bug 2: Điều kiện < hay <=?

Phụ thuộc vào convention "khoảng đóng" hay "khoảng nửa mở":

• Closed [lo, hi]: dùng while (lo <= hi) + hi = mid - 1
• Half-open [lo, hi): dùng while (lo < hi) + hi = mid

Đây là 2 style khác nhau, miễn sao nhất quán trong code. Đừng mix.

Bug 3: Tràn số khi tính mid

// ❌ Trong Java/C++, nếu lo+hi vượt INT_MAX thì tràn
const mid = (lo + hi) / 2;  // BAD in Java/C++

// ✅ Dùng cách này — luôn an toàn
const mid = lo + Math.floor((hi - lo) / 2);

JS dùng số 64-bit nên thực tế hiếm gặp tràn, nhưng quen tay viết cách an toàn để chuyển ngôn ngữ khác không bị bug.

8.4 Lower bound & Upper bound — biến thể quan trọng

Khi mảng có phần tử trùng, "find target" không đủ — ta cần biết:

• Lower bound: vị trí đầu tiên của phần tử ≥ target
• Upper bound: vị trí đầu tiên của phần tử > target

// arr = [1, 2, 4, 4, 4, 5, 7]
//        0  1  2  3  4  5  6
// lowerBound(arr, 4) = 2
// upperBound(arr, 4) = 5
// Số lần xuất hiện của 4 = upperBound - lowerBound = 3

// Lower bound — vị trí đầu tiên có arr[i] >= target
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;  // hi là exclusive
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else                   hi = mid;
  }
  return lo;  // lo === hi
}

// Upper bound — vị trí đầu tiên có arr[i] > target
function upperBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] <= target) lo = mid + 1;
    else                    hi = mid;
  }
  return lo;
}

Ứng dụng

• Đếm số xuất hiện: upperBound(target) - lowerBound(target)
• Tìm range: bài "Find First and Last Position of Element"
• Insert position: chèn target vào mảng đã sort, lowerBound chính là vị trí chèn

8.5 Search in Rotated Sorted Array

Mảng sort tăng nhưng bị "xoay" tại điểm bí ẩn: [4,5,6,7,0,1,2] (đã sort rồi xoay). Tìm target trong O(log n).

Insight: ít nhất một trong 2 nửa luôn đã sort. Ta xác định nửa nào sort, kiểm tra target có thuộc nửa đó không, rồi chọn hướng tìm.

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;

    // Nửa trái đã sort?
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else                                            lo = mid + 1;
    }
    // Nửa phải đã sort
    else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else                                            hi = mid - 1;
    }
  }
  return -1;
}

Tìm minimum trong Rotated Sorted Array

function findMin(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] > nums[hi]) lo = mid + 1;  // min ở nửa phải
    else                      hi = mid;       // min ở nửa trái (bao gồm mid)
  }
  return nums[lo];
}

8.6 Binary Search trên không gian đáp án — Pattern vàng

Đây là kỹ thuật advanced — không search trên mảng input, mà search trên không gian đáp án.

Khi nào dùng?

Khi bài toán có dạng:

• "Tìm giá trị nhỏ nhất / lớn nhất sao cho [điều kiện]"
• Hàm check(value) kiểm tra value có thoả không, là monotonic (nếu value k thoả thì k+1 cũng thoả, hoặc ngược lại)

Bài kinh điển: Capacity to Ship Packages

Có n gói hàng, mỗi gói có trọng lượng. Ta có D ngày để ship hết. Mỗi ngày ship liên tiếp các gói (theo thứ tự mảng) không vượt quá capacity của tàu. Tìm capacity nhỏ nhất.

function shipWithinDays(weights, days) {
  // Đáp án nằm trong [max(weights), sum(weights)]
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);

  function canShip(cap) {
    let need = 1, used = 0;
    for (const w of weights) {
      if (used + w > cap) {
        need++;
        used = 0;
      }
      used += w;
    }
    return need <= days;
  }

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canShip(mid)) hi = mid;       // có thể nhỏ hơn
    else              lo = mid + 1;
  }
  return lo;
}

Bài: Koko Eating Bananas

// Koko có piles bananas, có H giờ. Mỗi giờ ăn k chuối từ 1 đống.
// Tìm k nhỏ nhất để ăn hết trong H giờ.
function minEatingSpeed(piles, h) {
  let lo = 1, hi = Math.max(...piles);

  function canEat(k) {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / k);
    return hours <= h;
  }

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canEat(mid)) hi = mid;
    else             lo = mid + 1;
  }
  return lo;
}

let lo = MIN_POSSIBLE, hi = MAX_POSSIBLE;
while (lo < hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  if (check(mid)) hi = mid;       // tìm minimum thoả mãn
  // hoặc
  // if (check(mid)) lo = mid + 1;  // tìm maximum thoả mãn (rồi lo cuối là min không thoả → lo-1)
  else lo = mid + 1;
}
return lo;

8.7 Ternary Search — cho hàm unimodal

Khi hàm có dạng "núi" (tăng rồi giảm) hoặc "thung lũng", ternary search tìm peak trong O(log n) bằng chia 3.

// Tìm peak của mảng unimodal
function ternarySearch(f, lo, hi) {
  while (hi - lo > 2) {
    const m1 = lo + Math.floor((hi - lo) / 3);
    const m2 = hi - Math.floor((hi - lo) / 3);
    if (f(m1) < f(m2)) lo = m1;
    else               hi = m2;
  }
  // Khi range rất nhỏ, kiểm tra trực tiếp
  let best = lo;
  for (let i = lo + 1; i <= hi; i++) {
    if (f(i) > f(best)) best = i;
  }
  return best;
}

Ternary search cũng có thể dùng cho bài "Find Peak Element" trên mảng (LeetCode 162) — nhưng binary search đủ xài.

8.8 Exponential Search — khi không biết kích thước

Trên data stream / unbounded array, ta chưa biết độ dài. Exponential search: (1) tăng index gấp đôi đến khi arr[i] >= target, (2) binary search trong [i/2, i].

function exponentialSearch(arr, target) {
  if (arr[0] === target) return 0;
  let i = 1;
  while (i < arr.length && arr[i] < target) i *= 2;

  // Binary search trong [i/2, min(i, n-1)]
  let lo = Math.floor(i / 2);
  let hi = Math.min(i, arr.length - 1);
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else                   hi = mid - 1;
  }
  return -1;
}
// Time: O(log p), p = vị trí của target

8.9 Search trong Matrix sorted

Matrix loại 1: hàng và cột đều sort, đầu hàng > cuối hàng trên

Coi như 1 mảng phẳng đã sort → binary search 1D với index conversion.

function searchMatrix(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m * n - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    const r = Math.floor(mid / n), c = mid % n;
    if (matrix[r][c] === target) return true;
    if (matrix[r][c] < target) lo = mid + 1;
    else                       hi = mid - 1;
  }
  return false;
}
// Time: O(log(m*n))

Matrix loại 2: hàng/cột sort nhưng KHÔNG nối nhau

Bắt đầu từ góc top-right hoặc bottom-left, đi từng bước → O(m + n).

function searchMatrix2(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let r = 0, c = n - 1;  // top-right corner
  while (r < m && c >= 0) {
    if (matrix[r][c] === target) return true;
    if (matrix[r][c] > target)  c--;  // loại cột
    else                         r++;  // loại hàng
  }
  return false;
}

Bài tập

nums = [5,7,7,8,8,10], target = 8 → [3, 4]

Tổng kết chương 8

• ✅ Linear Search O(n) — không cần sort, đủ tốt cho n nhỏ
• ✅ Binary Search O(log n) — yêu cầu mảng sort
• ✅ Tránh off-by-one: dùng template lo <= hi + mid ± 1
• ✅ Lower/Upper bound: tìm "đầu" / "cuối" của khoảng phần tử = target
• ✅ Rotated Sorted Array: xác định nửa sort, kiểm tra target có ở đó không
• ✅ Binary Search trên đáp án: pattern vàng cho bài tối ưu hoá có check monotonic
• ✅ Exponential Search cho data stream không biết kích thước
• ✅ Matrix sorted: 1D binary search hoặc top-right step