Thuật toán tìm kiếm nhị phân (Binary Search)

Ý tưởng

Binary Search (tìm kiếm nhị phân) chỉ hoạt động trên mảng đã được sắp xếp. Mỗi bước, ta so sánh phần tử cần tìm với phần tử ở giữa, sau đó loại bỏ một nửa mảng không cần xét.

Độ phức tạp

Trường hợp	Độ phức tạp
Tốt nhất	O(1)
Trung bình	O(log n)
Tệ nhất	O(log n)
Bộ nhớ	O(1)

Cài đặt bằng JavaScript

function binarySearch(arr, target) {
    let left = 0
    let right = arr.length - 1

    while (left <= right) {
        const mid = Math.floor((left + right) / 2)

        if (arr[mid] === target) return mid
        if (arr[mid] < target) left = mid + 1
        else right = mid - 1
    }

    return -1
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7))
// → 3

Lưu ý

• Mảng phải được sắp xếp trước.
• Khi mảng nhỏ, tìm kiếm tuyến tính có khi còn nhanh hơn vì chi phí của các phép so sánh.
• Có thể mở rộng để tìm cận trên (upper_bound) và cận dưới (lower_bound).