Tìm kiếm nhị phân (binary search): giải thích dễ hiểu, code C++ và Python

Tìm kiếm nhị phân là gì?

Tìm kiếm nhị phân (binary search) là thuật toán tìm vị trí của một giá trị x trong mảng đã sắp xếp. Thay vì xét lần lượt từng phần tử như tìm kiếm tuần tự (linear search), ta nhìn vào phần tử ở giữa đoạn đang xét:

• Nếu phần tử giữa bằng x: đã tìm thấy.
• Nếu phần tử giữa nhỏ hơn x: x chỉ có thể nằm ở nửa bên phải, bỏ nửa bên trái.
• Nếu phần tử giữa lớn hơn x: x chỉ có thể nằm ở nửa bên trái, bỏ nửa bên phải.

Lặp lại cho tới khi tìm thấy x, hoặc đoạn đang xét không còn phần tử nào, tức là x không có trong mảng.

Ý tưởng qua trò đoán số

Bạn nghĩ một số từ 1 đến 100. Mình đoán, còn bạn chỉ trả lời “lớn hơn”, “nhỏ hơn” hoặc “đúng”. Cách đoán tốt nhất là luôn đoán số ở giữa: 50, rồi 25 hoặc 75, rồi cứ thế chia đôi. Mỗi câu trả lời loại được một nửa số khả năng, nên chỉ cần tối đa 7 lần đoán, vì 2⁷ = 128 ≥ 100. Tìm kiếm nhị phân làm đúng như vậy, chỉ khác là “đoán” trên một mảng đã sắp xếp.

Ví dụ từng bước

Tìm x = 23 trong mảng 10 phần tử đã sắp xếp, vị trí đánh số từ 0: a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91].

Chỉ cần 3 lần so sánh. Tìm tuần tự từ đầu mảng phải xét 6 phần tử, từ vị trí 0 đến vị trí 5.

Code tìm kiếm nhị phân bằng C++ và Python

Hàm trả về vị trí của x, hoặc -1 nếu x không có trong mảng. lo và hi là hai đầu của đoạn đang xét; vòng lặp dừng khi lo > hi, tức là đoạn đã rỗng.

#include <iostream>
#include <vector>
using namespace std;

// Trả về vị trí của x trong mảng a (đã sắp xếp tăng dần), không có thì trả về -1
int binarySearch(const vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // tránh tràn số khi lo + hi quá lớn
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1;  // x nằm ở nửa bên phải
        else hi = mid - 1;             // x nằm ở nửa bên trái
    }
    return -1;
}

int main() {
    vector<int> a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    cout << binarySearch(a, 23) << "\n";  // 5
    cout << binarySearch(a, 7) << "\n";   // -1
    return 0;
}

def binary_search(a, x):
    """Trả về vị trí của x trong danh sách a (đã sắp xếp tăng dần), không có thì trả về -1."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1  # x nằm ở nửa bên phải
        else:
            hi = mid - 1  # x nằm ở nửa bên trái
    return -1


a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(a, 23))  # 5
print(binary_search(a, 7))   # -1

Chạy chương trình sẽ in ra 5 và -1. Trong Python, số nguyên không bị tràn, nên viết (lo + hi) // 2 là được. Trong C++ và Java thì nên viết lo + (hi - lo) / 2, lý do ở phần lỗi hay gặp.

Độ phức tạp

Sau mỗi bước, đoạn đang xét chỉ còn khoảng một nửa. Từ n phần tử, sau k bước còn khoảng n / 2k phần tử, nên số bước tối đa vào khoảng log₂ n:

• Thời gian: O(log n).
• Bộ nhớ: O(1) với bản dùng vòng lặp ở trên.

Số lần so sánh tối đa của tìm kiếm nhị phân là ⌊log₂ n⌋ + 1. Mảng càng lớn thì cách biệt với tìm tuần tự càng lớn.

Hàm có sẵn: lower_bound và bisect

Khi làm bài, bạn thường không cần tự viết lại. C++ có lower_bound, upper_bound và binary_search trong thư viện <algorithm>; Python có module bisect.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    // lower_bound: vị trí đầu tiên có giá trị >= x
    int i = lower_bound(a.begin(), a.end(), 23) - a.begin();
    int j = lower_bound(a.begin(), a.end(), 7) - a.begin();
    cout << i << " " << j << "\n";                          // 5 2
    cout << binary_search(a.begin(), a.end(), 23) << "\n";  // 1 (có 23)
    return 0;
}

import bisect

a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# bisect_left: vị trí đầu tiên có giá trị >= x
print(bisect.bisect_left(a, 23), bisect.bisect_left(a, 7))  # 5 2

• lower_bound (C++) và bisect_left (Python): vị trí đầu tiên có giá trị ≥ x. Với x = 7, kết quả là 2 (phần tử 8). Đó cũng là chỗ chèn 7 vào mà mảng vẫn tăng dần.
• upper_bound và bisect_right: vị trí đầu tiên có giá trị > x.
• binary_search của C++ chỉ trả lời có hay không (true / false), không cho biết vị trí.

Lỗi hay gặp

Không chỉ để tìm trong mảng

Ý tưởng chia đôi dùng được cho mọi bài có điều kiện đơn điệu: nếu một giá trị thỏa điều kiện thì mọi giá trị lớn hơn nó cũng thỏa, hoặc ngược lại. Khi đó ta tìm kiếm nhị phân trên chính đáp án. Ví dụ: tìm số nguyên k lớn nhất có k² ≤ N, hay thời gian nhỏ nhất để làm xong mọi việc. Dạng này rất hay gặp trong đề thi học sinh giỏi Tin học và trong phỏng vấn.

Luyện ngay trên Big-O Coding

Các bài dưới đây có dùng tìm kiếm nhị phân, làm trực tiếp trên trang luyện thuật toán của Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::lower_bound
• Python docs: bisect
• cp-algorithms: Binary search
• Google Research: lỗi tràn số trong tìm kiếm nhị phân (2006)