Bài 21.3: Tìm kiếm nhị phân binary_search trong C++

Chào mừng các bạn quay trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng nhau khám phá một trong những giải thuật tìm kiếm mạnh mẽ và hiệu quả nhất khi làm việc với dữ liệu đã được sắp xếp: Tìm kiếm nhị phân (Binary Search). C++ Standard Library (STL) cung cấp cho chúng ta một công cụ tiện lợi để thực hiện điều này: hàm binary_search.

Tại sao cần Tìm kiếm nhị phân?

Trong thế giới lập trình, việc tìm kiếm một phần tử nào đó trong một tập hợp dữ liệu là một tác vụ cực kỳ phổ biến. Phương pháp đơn giản nhất là Tìm kiếm tuyến tính (Linear Search): đi qua từng phần tử một từ đầu đến cuối cho đến khi tìm thấy hoặc hết tập hợp. Phương pháp này luôn đúng, nhưng với tập dữ liệu lớn, nó có thể rất chậm.

Ví dụ, để tìm một số trong danh sách 1 triệu số chưa sắp xếp, trong trường hợp xấu nhất, bạn có thể phải kiểm tra cả 1 triệu số!

Tìm kiếm nhị phân ra đời để giải quyết vấn đề hiệu suất này, nhưng với một điều kiện tiên quyết rất quan trọng: dữ liệu phải được sắp xếp!

Tìm kiếm nhị phân hoạt động như thế nào?

Hãy tưởng tượng bạn đang tìm một từ trong một cuốn từ điển dày. Bạn không bắt đầu từ trang đầu tiên và đọc từng từ một đúng không? Chắc chắn là không! Bạn sẽ:

  1. Mở cuốn từ điển ra ở khoảng giữa.
  2. Xem từ ở trang đó.
  3. Nếu từ cần tìm nhỏ hơn từ đang xem, bạn biết nó phải nằm ở nửa đầu cuốn từ điển.
  4. Nếu từ cần tìm lớn hơn từ đang xem, bạn biết nó phải nằm ở nửa sau.
  5. Bạn loại bỏ nửa không chứa từ đó và lặp lại quá trình trên với nửa còn lại cho đến khi tìm thấy từ hoặc không còn trang nào để tìm.

Đây chính là ý tưởng cốt lõi của tìm kiếm nhị phân: chia để trị (divide and conquer). Ở mỗi bước, nó loại bỏ được một nửa số phần tử còn lại, giúp giảm đáng kể số bước tìm kiếm.

Về mặt hiệu suất, tìm kiếm nhị phân có độ phức tạp thời gian là O(log n), trong khi tìm kiếm tuyến tính là O(n). Với 1 triệu phần tử:

  • Tìm kiếm tuyến tính: Tối đa 1.000.000 bước.
  • Tìm kiếm nhị phân: log₂(1.000.000) ≈ 20 bước!

Sự khác biệt này trở nên khổng lồ khi dữ liệu ngày càng lớn.

Sử dụng binary_search trong C++

C++ cung cấp hàm binary_search trong thư viện <algorithm> để thực hiện tìm kiếm nhị phân một cách tiện lợi.

binary_search làm gì?

Hàm này kiểm tra xem một phạm vi (range) đã được sắp xếp có chứa một giá trị cụ thể hay không. Nó chỉ trả về true (nếu tìm thấy) hoặc false (nếu không tìm thấy). Nó không cho biết vị trí của phần tử (nếu có).

Cú pháp cơ bản
#include <algorithm> // Cần include thư viện này
#include <vector>    // hoặc bất kỳ container nào bạn dùng
#include <iostream>

// ...
bool found = binary_search(first, last, value);

Trong đó:

  • first, last: Là các iterator định nghĩa phạm vi tìm kiếm (thường là container.begin() và container.end()). Phạm vi này là [first, last), tức là bao gồm first nhưng không bao gồm last.
  • value: Là giá trị bạn muốn tìm kiếm.

Điều quan trọng nhất cần nhớ: Phạm vi [first, last) PHẢI được sắp xếp theo thứ tự tăng dần (mặc định sử dụng toán tử <) hoặc theo một tiêu chí sắp xếp nhất định. Nếu không, kết quả trả về là không xác định (undefined behavior) hoặc sai.

Ví dụ 1: Tìm kiếm thành công trong vector

Hãy xem một ví dụ đơn giản với vector<int> đã được sắp xếp.

#include <iostream>
#include <vector>
#include <algorithm> // For binary_search

int main() {
    vector<int> sorted_numbers = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

    int value_to_find = 50;

    // Sử dụng binary_search
    bool found = binary_search(sorted_numbers.begin(), sorted_numbers.end(), value_to_find);

    if (found) {
        cout << "Gia tri " << value_to_find << " duoc tim thay trong vector." << endl;
    } else {
        cout << "Gia tri " << value_to_find << " khong duoc tim thay trong vector." << endl;
    }

    return 0;
}
  • Giải thích code:
    • Chúng ta khởi tạo một vector tên là sorted_numbers với các số đã được sắp xếp.
    • Biến value_to_find chứa giá trị cần tìm (50).
    • Hàm binary_search được gọi với phạm vi từ sorted_numbers.begin() đến sorted_numbers.end() và giá trị 50.
    • Vì 50 có trong vector, binary_search trả về true, và chương trình in ra thông báo "Gia tri 50 duoc tim thay...".
Ví dụ 2: Tìm kiếm giá trị không tồn tại

Bây giờ, hãy thử tìm một giá trị không có trong vector đó.

#include <iostream>
#include <vector>
#include <algorithm> // For binary_search

int main() {
    vector<int> sorted_numbers = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

    int value_to_find = 55; // Giá trị này không có trong vector

    // Sử dụng binary_search
    bool found = binary_search(sorted_numbers.begin(), sorted_numbers.end(), value_to_find);

    if (found) {
        cout << "Gia tri " << value_to_find << " duoc tim thay trong vector." << endl;
    } else {
        cout << "Gia tri " << value_to_find << " khong duoc tim thay trong vector." << endl;
    }

    return 0;
}
  • Giải thích code:
    • Tương tự ví dụ trước, nhưng lần này chúng ta tìm giá trị 55.
    • Vì 55 không tồn tại trong vector, binary_search sẽ thực hiện quá trình tìm kiếm nhị phân và kết luận rằng nó không có mặt.
    • Hàm trả về false, và chương trình in ra thông báo "Gia tri 55 khong duoc tim thay...".
Ví dụ 3: Với container khác (ví dụ array)

binary_search hoạt động trên mọi phạm vi được định nghĩa bởi iterator phù hợp, không chỉ vector. Hãy thử với array.

#include <iostream>
#include <array>     // For array
#include <algorithm> // For binary_search
#include <string>    // For string

int main() {
    array<string, 5> sorted_words = {"apple", "banana", "cherry", "date", "elderberry"}; // Đã sắp xếp theo alphabet

    string target_word = "cherry";

    // Sử dụng binary_search
    bool found = binary_search(sorted_words.begin(), sorted_words.end(), target_word);

    if (found) {
        cout << "Tu '" << target_word << "' duoc tim thay." << endl;
    } else {
        cout << "Tu '" << target_word << "' khong duoc tim thay." << endl;
    }

    return 0;
}
  • Giải thích code:
    • Chúng ta dùng array chứa các chuỗi string đã sắp xếp theo thứ tự từ điển.
    • Tìm kiếm từ "cherry".
    • Hàm binary_search hoạt động bình thường với các iterator của array và kiểu dữ liệu string, trả về true.
Ví dụ 4: Điều gì xảy ra nếu dữ liệu KHÔNG SẮP XẾP?

Đây là lỗi phổ biến nhất khi sử dụng binary_search. Nếu bạn gọi nó trên dữ liệu chưa được sắp xếp, kết quả sẽ không đáng tin cậy.

#include <iostream>
#include <vector>
#include <algorithm> // For binary_search, sort

int main() {
    vector<int> unsorted_numbers = {50, 10, 80, 30, 60, 20, 100, 40, 90, 70}; // CHƯA SẮP XẾP!

    int value_to_find = 20;

    cout << "Tim kiem tren du lieu CHUA SAP XEP:" << endl;
    bool found_unsorted = binary_search(unsorted_numbers.begin(), unsorted_numbers.end(), value_to_find);

    if (found_unsorted) {
        cout << "Gia tri " << value_to_find << " duoc tim thay (KET QUA CO THE SAI!)." << endl;
    } else {
        cout << "Gia tri " << value_to_find << " khong duoc tim thay (KET QUA CO THE SAI!)." << endl;
    }

    cout << "\nSap xep du lieu..." << endl;
    sort(unsorted_numbers.begin(), unsorted_numbers.end()); // Sắp xếp vector

    cout << "Tim kiem tren du lieu DA SAP XEP:" << endl;
    bool found_sorted = binary_search(unsorted_numbers.begin(), unsorted_numbers.end(), value_to_find);

    if (found_sorted) {
        cout << "Gia tri " << value_to_find << " duoc tim thay (KET QUA CHINH XAC)." << endl;
    } else {
        cout << "Gia tri " << value_to_find << " khong duoc tim thay (KET QUA CHINH XAC)." << endl;
    }


    return 0;
}
  • Giải thích code:
    • Chúng ta tạo một vector unsorted_numbers chưa được sắp xếp.
    • Lần gọi binary_search đầu tiên trên unsorted_numbers có thể cho kết quả sai. Nó có thể báo tìm thấy hoặc không tìm thấy 20, và kết quả đó không đáng tin cậy.
    • Sau đó, chúng ta sử dụng sort (cũng từ <algorithm>) để sắp xếp vector. Bây giờ vector đã là `{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}}$.
    • Lần gọi binary_search thứ hai trên vector đã sắp xếp sẽ cho kết quả chính xác (tìm thấy 20).
    • Bài học quan trọng: Luôn đảm bảo phạm vi tìm kiếm được sắp xếp trước khi gọi binary_search!
Về hàm so sánh (Comparator)

Phiên bản mặc định của binary_search sử dụng toán tử < để so sánh các phần tử và giá trị tìm kiếm. Nếu bạn làm việc với các kiểu dữ liệu phức tạp hoặc cần một tiêu chí sắp xếp khác (ví dụ: sắp xếp giảm dần, sắp xếp theo một trường cụ thể của đối tượng), bạn có thể sử dụng phiên bản overload của binary_search nhận thêm một hàm so sánh nhị phân (binary predicate). Hàm này nhận hai đối số và trả về true nếu đối số thứ nhất được coi là "nhỏ hơn" đối số thứ hai theo tiêu chí của bạn.

// Ví dụ về hàm so sánh tùy chỉnh (không cần code đầy đủ, chỉ minh họa khái niệm)
bool compare_descending(int a, int b) {
    return a > b; // Sắp xếp giảm dần
}

// ... trong main() hoặc một hàm khác
// vector<int> sorted_descending_numbers = {100, 90, ..., 10};
// int value_to_find = 50;
// bool found = binary_search(sorted_descending_numbers.begin(), sorted_descending_numbers.end(), value_to_find, compare_descending);

Lưu ý: Khi sử dụng hàm so sánh tùy chỉnh, phạm vi tìm kiếm của bạn cũng phải được sắp xếp dựa trên cùng một tiêu chí đó.

Bài tập ví dụ: C++ Bài 10.B1: Tổng bằng X

Cho một dãy số nguyên đã được sắp xếp không giảm \(a\) có \(n\) phần tử. Hãy tìm hai vị trí khác nhau bất kỳ sao cho tổng của hai phần tử ở hai vị trí đó có giá trị là \(x\).

INPUT FORMAT

Dòng đầu tiên chứa số nguyên \(n\) và \(x\) (\( 1 \leq n \leq 10^6\)).

Dòng thứ hai chứa \(n\) số nguyên, mỗi số các nhau một dấu cách \((1 \leq a_i, x < 10^{9})\).

OUTPUT FORMAT

In ra hai số nguyên là vị trí tìm được, nếu không có đáp án in ra No solution.

Ví dụ:

Input
7 16
2 5 6 8 10 12 15
Output
3 5
Giải thích ví dụ mẫu
  • Ví dụ 1:
    • Dữ liệu: a = [2, 5, 6, 8, 10, 12, 15], x = 16
    • Giải thích: Tìm hai chỉ số sao cho tổng hai phần tử tại các chỉ số đó bằng 16. Vị trí 3 (6) và 5 (10) là một cặp hợp lệ vì 6 + 10 = 16.

<br>

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House Tuyệt vời, đây là bài tập kinh điển sử dụng kỹ thuật hai con trỏ trên mảng đã sắp xếp. Yêu cầu là tìm hai vị trí khác nhau có tổng bằng x.

Hướng dẫn giải bài này bằng C++ (không cung cấp code hoàn chỉnh):

  1. Đọc Input:

    • Đọc hai số nguyên n và x.
    • Đọc n số nguyên vào một container std phù hợp, ví dụ như vector. Mảng đã được đảm bảo sắp xếp không giảm.

  2. Xác định Kỹ thuật:

    • Vì mảng đã được sắp xếp, kỹ thuật "hai con trỏ" (two-pointer technique) là lựa chọn tối ưu nhất về mặt thời gian. Kỹ thuật này có độ phức tạp O(n).

  3. Áp dụng Kỹ thuật Hai Con Trỏ:

    • Khởi tạo hai con trỏ (hoặc chỉ số): một con trỏ left ở vị trí đầu tiên của mảng (chỉ số 0), và một con trỏ right ở vị trí cuối cùng của mảng (chỉ số n-1).
    • Sử dụng một vòng lặp while chạy chừng nào con trỏ left còn nhỏ hơn con trỏ right (left < right). Điều kiện left < right đảm bảo chúng ta luôn xét hai vị trí khác nhau.
    • Bên trong vòng lặp:
      • Tính tổng của hai phần tử tại vị trí left và right: current_sum = a[left] + a[right].
      • So sánh current_sum với x:
        • Nếu current_sum == x: Chúng ta đã tìm thấy một cặp có tổng bằng x. Đây chính là đáp án. In ra vị trí của chúng (nhớ là chỉ số trong đề bài là 1-based, nên cần in left + 1 và right + 1). Sau đó, dừng chương trình.
        • Nếu current_sum < x: Tổng hiện tại quá nhỏ. Để tăng tổng, chúng ta cần một số lớn hơn. Vì mảng đã sắp xếp, cách để tăng tổng là di chuyển con trỏ left sang phải (left++) để lấy một phần tử lớn hơn ở bên trái.
        • Nếu current_sum > x: Tổng hiện tại quá lớn. Để giảm tổng, chúng ta cần một số nhỏ hơn. Cách để giảm tổng là di chuyển con trỏ right sang trái (right--) để lấy một phần tử nhỏ hơn ở bên phải.

  4. Xử lý Trường hợp Không Có Đáp án:

    • Nếu vòng lặp while (left < right) kết thúc (tức là left >= right) mà chúng ta vẫn chưa tìm thấy cặp nào có tổng bằng x, điều đó có nghĩa là không có cặp nào như vậy tồn tại trong mảng.
    • Sau khi vòng lặp kết thúc, nếu chưa tìm được đáp án, in ra "No solution".

  5. Lưu ý về Tối ưu I/O (không bắt buộc nhưng khuyến khích cho bài lớn):

    • Với n lên đến 10^6, việc đọc/ghi dữ liệu có thể tốn thời gian. Có thể sử dụng ios_base::sync_with_stdio(false); cin.tie(NULL); ở đầu hàm main để tăng tốc độ đọc/ghi qua cin và cout.

  6. Kiểu dữ liệu:

    • Các phần tử a_i và x có thể lên tới gần 10^9. Tổng của hai phần tử có thể lên tới gần 2 10^9. Kiểu dữ liệu int chuẩn 32-bit thường có phạm vi đủ lớn (khoảng -2 10^9 đến +2 * 10^9). Tuy nhiên, để an toàn hơn, đặc biệt khi tính tổng, có thể xem xét sử dụng long long cho biến lưu tổng current_sum, mặc dù int có thể đủ trong trường hợp này dựa trên ràng buộc đề bài 1 <= a_i, x < 10^9.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.