Tìm kiếm nhị phân: chia đôi để tìm thật nhanh

Giống như mở từ điển: mở giữa cuốn, xem từ cần tìm nằm nửa nào rồi bỏ nửa còn lại. Mỗi bước loại được một nửa nên chỉ cần O(log n) bước. Điều kiện là dãy phải được sắp xếp.

Code mẫu

int l = 0, r = n - 1, kq = -1;
while (l <= r) {
    int m = l + (r - l) / 2;
    if (a[m] == x) { kq = m; break; }
    if (a[m] < x) l = m + 1;
    else r = m - 1;
}

Lỗi hay gặp

• Gán l = m thay vì l = m + 1, gây vòng lặp vô hạn.
• Quên sắp xếp dãy trước khi tìm.

Với n = 10⁶, tìm kiếm nhị phân chỉ cần khoảng 20 bước, trong khi duyệt lần lượt có thể tốn tới một triệu bước.