Binary Search (Tìm Kiếm Nhị Phân)

Binary Search là kỹ thuật tìm kiếm trên mảng đã sắp xếp bằng cách chia đôi không gian tìm kiếm sau mỗi bước. Độ phức tạp: O(log N).

The Bug That Haunted Java for 9 Years

Hầu hết mọi người (kể cả các kỹ sư Google thời xưa) đều viết mid như sau:

int mid = (left + right) / 2;

Vấn đề là gì? Nếu left và right đều là số dương rất lớn (gần INT_MAX), tổng left + right có thể vượt quá giới hạn của kiểu int (Integer Overflow), dẫn đến kết quả âm!

Giải pháp chuẩn:

int mid = left + (right - left) / 2;

Các Template Chuẩn (Phải Học Thuộc)

1. Tìm Giá Trị Chính Xác (Basic)

Trả về index của target hoặc -1 nếu không tìm thấy.

C++

int binarySearch(int nums[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Java

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Prevent overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Python

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

2. Tìm Vị Trí Trái Nhất (Lower Bound)

Tìm index đầu tiên mà tại đó nums[index] >= target.

int lowerBound(int nums[], int n, int target) {
    int left = 0, right = n; // Lưu ý right = n
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

3. Tìm Vị Trí Phải Nhất (Upper Bound)

Tìm index đầu tiên mà tại đó nums[index] > target.

int upperBound(int nums[], int n, int target) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) right = mid;
        else left = mid + 1;
    }
    return left;
}