🔢 Algorithms✍️ Khoa📅 19/04/2026☕ 6 phút đọc

Algorithms: Binary Search

Dấu hiệu nhận biết:

  • Search trong sorted array
  • Bài có monotonic property: "tìm giá trị nhỏ nhất thỏa điều kiện X"
  • Search space có thể chia đôi một cách có ý nghĩa
  • Câu hỏi dạng "find first/last position"

Nguyên tắc cốt lõi: Binary search không phải chỉ dùng cho array. Bất kỳ search space nào có monotonic predicate đều có thể dùng binary search.

2. Template chuẩn (tránh bug)

Template 1: Tìm exact value

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2 // tránh overflow
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

Template 2: Tìm first position thỏa điều kiện (Lower Bound)

// Tìm index nhỏ nhất mà nums[i] >= target
func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums) // right = len, không phải len-1
    for left < right {           // left < right, không phải <=
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid // không phải mid-1
        }
    }
    return left // left == right tại điểm hội tụ
}
nums = [1, 3, 5, 7, 9], target = 5
       L              R
         mid=2 (5)     → right=2
       L  R
         mid=1 (3)    → left=2
          LR → return 2 ✓

Template 3: Tìm last position (Upper Bound)

// Tìm index lớn nhất mà nums[i] <= target
func upperBound(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left - 1 // last position <= target
}

3. Bài kinh điển

Find First and Last Position

func searchRange(nums []int, target int) []int {
    first := lowerBound(nums, target)
    if first == len(nums) || nums[first] != target {
        return []int{-1, -1}
    }
    last := upperBound(nums, target)
    return []int{first, last}
}

Search in Rotated Sorted Array

Original: [1, 2, 3, 4, 5, 6, 7]
Rotated:  [4, 5, 6, 7, 1, 2, 3]
                    ^
              pivot point

Key insight: Khi split ở mid, ít nhất 1 nửa luôn sorted.

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        // Left half sorted?
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1 // target trong left half
            } else {
                left = mid + 1
            }
        } else {
            // Right half sorted
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1 // target trong right half
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

Binary search không phải trên array, mà trên không gian đáp án.

Ví dụ: Koko Eating Bananas

  • Koko có thể ăn k chuối/giờ
  • Có h giờ, tìm k nhỏ nhất để ăn hết
k nhỏ → không đủ giờ (false)
k lớn → đủ giờ (true)
→ monotonic: false...false|true...true
→ tìm k nhỏ nhất cho true
func minEatingSpeed(piles []int, h int) int {
    canFinish := func(k int) bool {
        hours := 0
        for _, pile := range piles {
            hours += (pile + k - 1) / k // ceiling division
        }
        return hours <= h
    }

    left, right := 1, 0
    for _, pile := range piles {
        if pile > right {
            right = pile
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canFinish(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

Pattern chung cho answer-space BS:

func solveBS() int {
    left, right := minPossible, maxPossible
    for left < right {
        mid := left + (right-left)/2
        if feasible(mid) {
            right = mid   // tìm minimum thỏa điều kiện
            // hoặc: left = mid + 1  // tìm maximum thỏa điều kiện
        } else {
            left = mid + 1
            // hoặc: right = mid
        }
    }
    return left
}

Sqrt(x) — Binary search trên answer space

func mySqrt(x int) int {
    if x < 2 {
        return x
    }
    left, right := 1, x/2
    for left < right {
        mid := left + (right-left+1)/2 // +1 để tránh infinite loop khi left+1==right
        if mid*mid <= x {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

Find Peak Element

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[mid+1] {
            right = mid // peak ở phía left (bao gồm mid)
        } else {
            left = mid + 1 // nums[mid+1] > nums[mid] → peak ở phía right
        }
    }
    return left
}

4. Tại sao mid = left + (right-left)/2?

left=2147483646, right=2147483647
(left+right)/2 = overflow!
left + (right-left)/2 = 2147483646 + 0 = 2147483646 ✓

5. Common mistakes

Lỗi Nguyên nhân Fix
Infinite loop mid = (left+right)/2 với left = mid Dùng mid = left + (right-left+1)/2 khi left = mid
Off-by-one Nhầm right = len-1 vs right = len Template 1 dùng len-1, Template 2/3 dùng len
Quên check nums[first] != target LowerBound trả về vị trí insert, không phải found Luôn check sau khi BS
Conditions sai trong rotated search Nhầm <= và < khi check left/right sorted Vẽ diagram cụ thể để verify

💡 Interview: Khi bị hỏi "optimize từ O(n) xuống O(log n)", luôn nghĩ đến binary search. Câu hỏi "minimum/maximum value thỏa điều kiện" → answer-space binary search. Từ khóa: "sorted", "rotated sorted", "find minimum/maximum feasible".