Bài 16.3. Binary Search trên dãy liên tục và rời rạc

Chào mừng bạn đến với bài viết sâu hơn về một trong những thuật toán tìm kiếm kinh điển và mạnh mẽ nhất: Binary Search (Tìm kiếm nhị phân). Nếu bạn đã từng làm việc với dữ liệu được sắp xếp, khả năng cao bạn đã sử dụng hoặc ít nhất là nghe đến thuật toán này. Sức mạnh của Binary Search nằm ở khả năng giảm thiểu không gian tìm kiếm đi một nửa sau mỗi bước kiểm tra, mang lại hiệu quả vượt trội với độ phức tạp thời gian chỉ O(log n) so với O(n) của tìm kiếm tuyến tính.

Tuy nhiên, Binary Search không chỉ giới hạn trong việc tìm kiếm một phần tử trên một mảng đã sắp xếp đơn thuần. Nó là một kỹ thuật giải thuật có thể áp dụng trên bất kỳ không gian tìm kiếm nào mà có một tính chất đơn điệu (monotonic property) cho phép ta loại bỏ một nửa không gian tìm kiếm sau mỗi lần thử. Không gian tìm kiếm này có thể là các chỉ số trong mảng, các giá trị nguyên, hoặc thậm chí là các giá trị thực trên một miền liên tục.

Trong bài viết này, chúng ta sẽ đi sâu vào:

Binary Search cơ bản trên dãy rời rạc (mảng đã sắp xếp).
Mở rộng ứng dụng của Binary Search trên dãy rời rạc nhưng không phải là mảng trực tiếp (tìm kiếm trên miền giá trị nguyên).
Áp dụng Binary Search trên miền giá trị liên tục (tìm kiếm trên số thực).

Hãy cùng bắt đầu!

1. Binary Search Cơ Bản trên Dãy Rời Rạc (Mảng)

Đây là ứng dụng phổ biến nhất của Binary Search. Giả sử bạn có một mảng arr gồm n phần tử đã được sắp xếp theo thứ tự tăng dần, và bạn muốn kiểm tra xem một giá trị target có tồn tại trong mảng đó hay không, hoặc tìm vị trí của nó.

Ý tưởng cốt lõi rất đơn giản:

Xác định một khoảng tìm kiếm ban đầu, bao gồm toàn bộ mảng: từ chỉ số left = 0 đến right = n-1.
Trong khi khoảng tìm kiếm còn hợp lệ (left <= right):
- Tính chỉ số trung tâm mid = left + (right - left) / 2. (Tại sao lại tính như vậy mà không phải (left + right) / 2? Để tránh nguy cơ tràn số nếu left và right quá lớn).
- So sánh phần tử tại vị trí mid (arr[mid]) với target:
  - Nếu arr[mid] == target: Tuyệt vời! Chúng ta đã tìm thấy phần tử. Trả về chỉ số mid.
  - Nếu arr[mid] < target: Phần tử tại mid nhỏ hơn giá trị cần tìm. Điều này có nghĩa là nếu target tồn tại, nó phải nằm ở nửa bên phải của mid. Vì arr[mid] đã được kiểm tra và không phải là target, chúng ta có thể loại bỏ mid và tất cả các phần tử bên trái nó. Cập nhật khoảng tìm kiếm mới: left = mid + 1.
  - Nếu arr[mid] > target: Phần tử tại mid lớn hơn giá trị cần tìm. Tương tự, nếu target tồn tại, nó phải nằm ở nửa bên trái của mid. Loại bỏ mid và tất cả các phần tử bên phải nó. Cập nhật khoảng tìm kiếm mới: right = mid - 1.
Nếu vòng lặp kết thúc mà không tìm thấy (left > right), điều đó có nghĩa là target không có trong mảng.

Hãy xem mã C++ cho thuật toán này:

#include <iostream>
#include <vector>
#include <algorithm> // Cần cho std::sort nếu mảng chưa sắp xếp

// Hàm thực hiện Binary Search trên vector các số nguyên đã sắp xếp
// Trả về chỉ số của phần tử nếu tìm thấy, ngược lại trả về -1
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1; // Khoảng tìm kiếm ban đầu: [0, n-1]

    while (left <= right) { // Khi khoảng tìm kiếm còn hợp lệ (bao gồm cả trường hợp left == right)
        // Tính chỉ số trung tâm an toàn để tránh tràn số
        int mid = left + (right - left) / 2;

        // So sánh phần tử tại mid với target
        if (arr[mid] == target) {
            // Tìm thấy phần tử
            return mid;
        } else if (arr[mid] < target) {
            // arr[mid] nhỏ hơn target, tìm kiếm ở nửa bên phải (loại bỏ mid)
            left = mid + 1;
        } else { // arr[mid] > target
            // arr[mid] lớn hơn target, tìm kiếm ở nửa bên trái (loại bỏ mid)
            right = mid - 1;
        }
    }

    // Vòng lặp kết thúc mà không tìm thấy, target không tồn tại trong mảng
    return -1;
}

int main() {
    std::vector<int> myVector = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    // Ví dụ tìm kiếm một phần tử có tồn tại
    int target1 = 23;
    int index1 = binarySearch(myVector, target1);
    if (index1 != -1) {
        std::cout << "Tim thay " << target1 << " tai chi so: " << index1 << std::endl; // Output: Tim thay 23 tai chi so: 5
    } else {
        std::cout << target1 << " khong co trong mang." << std::endl;
    }

    // Ví dụ tìm kiếm một phần tử không tồn tại
    int target2 = 50;
    int index2 = binarySearch(myVector, target2);
    if (index2 != -1) {
        std::cout << "Tim thay " << target2 << " tai chi so: " << index2 << std::endl;
    } else {
        std::cout << target2 << " khong co trong mang." << std::endl; // Output: 50 khong co trong mang.
    }

    return 0;
}

Giải thích Code:

Hàm binarySearch nhận vào một const std::vector<int>& arr (vector đã sắp xếp) và int target. Sử dụng const& để tránh sao chép tốn kém và đảm bảo vector không bị thay đổi.
left và right là các biến kiểu int đánh dấu phạm vi tìm kiếm (các chỉ số mảng). Ban đầu, chúng bao phủ toàn bộ mảng.
Vòng lặp while (left <= right) tiếp tục tìm kiếm cho đến khi phạm vi trở nên rỗng (khi left vượt qua right).
mid = left + (right - left) / 2; tính chỉ số ở giữa. Cách tính này an toàn hơn (left + right) / 2 khi left và right là các số nguyên dương lớn.
Ba nhánh if-else if-else xử lý kết quả so sánh arr[mid] và target, điều chỉnh left hoặc right để thu hẹp phạm vi tìm kiếm vào nửa phù hợp.
- left = mid + 1: Khi arr[mid] < target, chúng ta biết target (nếu có) phải nằm sau mid. Vì mid không phải là đáp án, ta loại bỏ nó bằng cách bắt đầu tìm kiếm từ mid + 1.
- right = mid - 1: Khi arr[mid] > target, chúng ta biết target (nếu có) phải nằm trước mid. Tương tự, mid không phải là đáp án, ta loại bỏ nó bằng cách kết thúc tìm kiếm tại mid - 1.
Nếu vòng lặp kết thúc mà không trả về, điều đó có nghĩa là target không được tìm thấy trong mảng, và hàm trả về -1.
Hàm main minh họa cách sử dụng hàm binarySearch với hai trường hợp: tìm thấy và không tìm thấy.

Biến thể của Binary Search trên mảng có thể bao gồm tìm kiếm vị trí xuất hiện đầu tiên/cuối cùng của một phần tử trùng lặp, hoặc tìm kiếm phần tử nhỏ nhất/lớn nhất thỏa mãn một điều kiện nào đó. Những biến thể này chỉ khác nhau ở cách xử lý khi arr[mid] == target và cách điều chỉnh left/right để đảm bảo tìm đúng ranh giới. Tuy nhiên, ý tưởng cốt lõi là vẫn dựa vào tính chất đơn điệu của mảng đã sắp xếp.

2. Binary Search trên Dãy Rời Rạc (Miền Giá Trị Nguyên)

Binary Search không chỉ giới hạn ở việc tìm kiếm chỉ số trong một mảng. Nó có thể được áp dụng để tìm kiếm một giá trị trên một miền giá trị nào đó (thường là các số nguyên) khi có một tính chất đơn điệu liên quan đến giá trị đó.

Ví dụ điển hình là bài toán tìm căn bậc hai nguyên của một số N, tức là tìm số nguyên không âm $x$ lớn nhất sao cho $x^2 \le N$.

Không gian tìm kiếm: Các số nguyên không âm $x$. Với số $N$ dương, $x$ chắc chắn nằm trong khoảng từ $0$ đến $N$. Vậy không gian tìm kiếm là các số nguyên trong đoạn $[0, N]$.
Tính chất đơn điệu: Hàm $f(x) = x^2$ là tăng đơn điệu với $x \ge 0$. Điều kiện $x^2 \le N$ có tính chất đơn điệu: nếu một số $x_0$ thỏa mãn $x_0^2 \le N$, thì tất cả các số $x < x_0$ cũng sẽ thỏa mãn tính chất đó ($(x)^2 < (x_0)^2 \le N$). Ngược lại, nếu $x_0^2 > N$, thì tất cả các số $x > x_0$ cũng sẽ thỏa mãn $(x)^2 > (x_0)^2 > N$. Điều này tạo ra một "điểm cắt" trong dãy số nguyên: các số bên trái thỏa mãn điều kiện, các số bên phải không thỏa mãn. Chúng ta đang tìm số lớn nhất nằm ở phía thỏa mãn.

Áp dụng Binary Search:

Xác định khoảng tìm kiếm cho giá trị $x$: left = 0, right = N.
Trong khi left <= right:
- Tính giá trị trung tâm mid = left + (right - left) / 2.
- Kiểm tra tính chất tại mid: mid * mid <= N.
  - Nếu mid * mid <= N: Giá trị mid có thể là đáp án (hoặc đáp án chính xác lớn hơn mid). Lưu mid là một ứng viên cho kết quả (ans = mid) và thử tìm một đáp án tốt hơn (lớn hơn) ở nửa bên phải: left = mid + 1.
  - Nếu mid * mid > N: Giá trị mid quá lớn. Đáp án chính xác phải nhỏ hơn mid. Tìm kiếm ở nửa bên trái: right = mid - 1.
Sau khi vòng lặp kết thúc, biến ans sẽ giữ giá trị nguyên lớn nhất thỏa mãn điều kiện.

Đây là mã C++:

#include <iostream>

// Hàm tìm căn bậc hai nguyên lớn nhất của một số nguyên không âm n
// Trả về số nguyên x lớn nhất sao cho x*x <= n
int integerSqrt(int n) {
    if (n < 0) {
        // Căn bậc hai không xác định với số âm (trong tập số thực)
        // Có thể ném ngoại lệ hoặc trả về giá trị đặc biệt tùy yêu cầu
        return -1; // Giả định trả về -1 cho trường hợp lỗi
    }
    if (n == 0) {
        return 0;
    }

    int left = 0;
    int right = n; // Không gian tìm kiếm cho giá trị căn: [0, n]
    int ans = 0;   // Biến lưu kết quả tiềm năng

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

        // Sử dụng kiểu long long cho mid * mid để tránh tràn số khi n lớn
        long long midSquared = (long long)mid * mid;

        if (midSquared <= n) {
            // mid có thể là đáp án, hoặc đáp án tốt hơn nằm ở phía bên phải
            ans = mid;       // Lưu mid là đáp án tiềm năng
            left = mid + 1;  // Tìm kiếm ở nửa bên phải
        } else {
            // mid quá lớn, đáp án phải nằm ở phía bên trái
            right = mid - 1; // Tìm kiếm ở nửa bên trái
        }
    }

    return ans; // ans là giá trị lớn nhất thỏa mãn mid*mid <= n
}

int main() {
    int num1 = 4;
    std::cout << "Can bac hai nguyen lon nhat cua " << num1 << " la: " << integerSqrt(num1) << std::endl; // Output: 2

    int num2 = 8;
    std::cout << "Can bac hai nguyen lon nhat cua " << num2 << " la: " << integerSqrt(num2) << std::endl; // Output: 2 (vi 2*2=4 <= 8, 3*3=9 > 8)

    int num3 = 0;
    std::cout << "Can bac hai nguyen lon nhat cua " << num3 << " la: " << integerSqrt(num3) << std::endl; // Output: 0

     int num4 = 25;
    std::cout << "Can bac hai nguyen lon nhat cua " << num4 << " la: " << integerSqrt(num4) << std::endl; // Output: 5

    int num5 = 100;
    std::cout << "Can bac hai nguyen lon nhat cua " << num5 << " la: " << integerSqrt(num5) << std::endl; // Output: 10

     int num6 = 2147483647; // INT_MAX
     std::cout << "Can bac hai nguyen lon nhat cua " << num6 << " la: " << integerSqrt(num6) << std::endl; // Output: 46340

    return 0;
}

Giải thích Code:

Hàm integerSqrt nhận vào một số nguyên n.
Chúng ta xác định phạm vi tìm kiếm cho giá trị căn: từ 0 đến n. left = 0, right = n. Lưu ý: right có thể là n/2 nếu n > 1 để tối ưu nhẹ, vì căn bậc hai của n không bao giờ lớn hơn n/2 (trừ n=1), nhưng n là một giới hạn an toàn và đơn giản.
Biến ans được sử dụng để lưu trữ giá trị mid cuối cùng mà thỏa mãn điều kiện mid*mid <= n. Đây là kỹ thuật phổ biến khi tìm kiếm một ranh giới (ví dụ: giá trị lớn nhất/nhỏ nhất thỏa mãn điều kiện).
Trong vòng lặp while (left <= right):
- Tính mid.
- Quan trọng: Sử dụng long long khi tính mid * mid để tránh tràn số nếu n (và do đó mid) là một số nguyên lớn (gần INT_MAX).
- Nếu midSquared <= n, điều này có nghĩa là mid thỏa mãn điều kiện. Vì chúng ta đang tìm số lớn nhất thỏa mãn, mid là một ứng viên tiềm năng (ans = mid), và chúng ta thử tìm số lớn hơn nữa ở nửa bên phải (left = mid + 1).
- Nếu midSquared > n, mid không thỏa mãn. Đáp án phải nhỏ hơn mid. Tìm kiếm ở nửa bên trái (right = mid - 1).
Khi vòng lặp kết thúc, ans sẽ chứa giá trị nguyên lớn nhất mà bình phương của nó nhỏ hơn hoặc bằng n.

Bài toán này cho thấy Binary Search có thể được áp dụng khi bạn có một không gian tìm kiếm có thể được "chia đôi" dựa trên việc kiểm tra một tính chất đơn điệu tại điểm giữa.

3. Binary Search trên Miền Giá Trị Liên Tục

Mở rộng hơn nữa, Binary Search có thể được sử dụng để tìm kiếm một giá trị thực trên một khoảng liên tục các số thực. Thay vì tìm kiếm một chỉ số hoặc một số nguyên, chúng ta tìm kiếm một giá trị thực $x$ thỏa mãn một điều kiện nào đó, thường là tìm một nghiệm xấp xỉ cho phương trình hoặc tìm điểm cực trị.

Không gian tìm kiếm: Một khoảng số thực $[a, b]$.
Tính chất đơn điệu: Cần có một hàm $f(x)$ hoặc một tính chất liên quan đến $x$ mà có tính chất đơn điệu trên khoảng $[a, b]$. Ví dụ, $f(x)$ là hàm tăng hoặc giảm đơn điệu.

Ví dụ: Tìm căn bậc hai của một số thực không âm $N$. Tức là tìm số thực $x \ge 0$ sao cho $x^2 \approx N$.

Không gian tìm kiếm: Các số thực $x \ge 0$. Một khoảng tìm kiếm hợp lý là $[0, N]$ nếu $N \ge 1$, hoặc $[0, 1]$ nếu $0 \le N < 1$. Để đơn giản, ta có thể lấy $[0, \max(N, 1.0)]$ hoặc thậm chí $[0, N+1]$ cho $N \ge 0$. Lấy $[0, N]$ cho $N \ge 0$ là ổn nếu ta xử lý trường hợp $N < 1$ hoặc $N=0$ riêng. Hoặc đơn giản hơn nữa, lấy $[0, \max(N, 1)]$ cho $N \ge 0$. Với $N \ge 0$, căn bậc hai sẽ nằm trong $[0, \max(N, 1)]$.
Tính chất đơn điệu: Hàm $f(x) = x^2$ là tăng đơn điệu trên miền $x \ge 0$.
Điều kiện: $x^2 \approx N$.

Áp dụng Binary Search trên số thực:

Xác định khoảng tìm kiếm cho giá trị $x$: left và right là các biến kiểu double. Ví dụ: left = 0.0, right = std::max(1.0, n).
Điều kiện dừng: Vì làm việc với số thực và độ chính xác giới hạn, ta không tìm kiếm cho đến khi left > right hay tìm được giá trị chính xác. Thay vào đó, ta lặp lại một số lần cố định (ví dụ: 100 lần) hoặc cho đến khi khoảng tìm kiếm right - left đủ nhỏ (nhỏ hơn một giá trị $\epsilon$ rất bé). Lặp cố định số lần là phổ biến và thường đủ cho hầu hết các bài toán.
Trong mỗi lần lặp:
- Tính giá trị trung tâm mid = left + (right - left) / 2.0. Sử dụng 2.0 để đảm bảo phép chia là chia số thực.
- Kiểm tra tính chất tại mid: mid * mid < n.
  - Nếu mid * mid < n: mid quá nhỏ. Căn bậc hai thật phải lớn hơn mid. Thu hẹp khoảng tìm kiếm vào nửa bên phải: left = mid.
  - Nếu mid * mid >= n: mid quá lớn hoặc chính xác. Căn bậc hai thật phải nhỏ hơn hoặc bằng mid. Thu hẹp khoảng tìm kiếm vào nửa bên trái: right = mid.
Sau khi lặp đủ số lần, cả left, right, và mid đều là các giá trị xấp xỉ căn bậc hai của $N$. Ta có thể trả về mid (hoặc left, right).

Lưu ý sự khác biệt trong cách cập nhật left và right: chúng ta dùng left = mid hoặc right = mid thay vì mid + 1 hay mid - 1 như trên số nguyên. Điều này là bởi vì mid có thể là giá trị cần tìm (hoặc rất gần với nó) và chúng ta đang làm việc trên một miền liên tục, không có "khoảng trống" giữa các giá trị.

Đây là mã C++:

#include <iostream>
#include <cmath>   // Cần cho std::sqrt (để so sánh) và std::max
#include <iomanip> // Cần cho std::fixed và std::setprecision

// Hàm tìm căn bậc hai của một số thực không âm n sử dụng Binary Search
// Lặp lại một số lần cố định để đạt độ chính xác mong muốn
double realSqrt(double n, int iterations) {
    if (n < 0) {
        std::cerr << "Loi: Khong the tinh can bac hai so am." << std::endl;
        return -1.0; // Giá trị lỗi
    }
    if (n == 0) {
        return 0.0;
    }

    // Khoảng tìm kiếm ban đầu cho giá trị căn x
    // Căn bậc hai của n (n>=0) nằm trong khoảng [0, max(n, 1)]
    double left = 0.0;
    double right = std::max(1.0, n); // Đảm bảo khoảng đủ lớn cho n < 1 và n >= 1

    for (int i = 0; i < iterations; ++i) {
        double mid = left + (right - left) / 2.0; // Tính giá trị trung tâm (số thực)

        if (mid * mid < n) {
            // mid quá nhỏ, căn thật nằm ở nửa bên phải [mid, right]
            left = mid;
        } else { // mid * mid >= n
            // mid quá lớn hoặc chính xác, căn thật nằm ở nửa bên trái [left, mid]
            right = mid;
        }
    }

    // Sau số lần lặp, left và right sẽ rất gần nhau và xấp xỉ căn bậc hai
    return left; // Có thể trả về left, right hoặc (left + right) / 2.0
}

int main() {
    double num1 = 4.0;
    int iters = 100; // Số lần lặp để đạt độ chính xác

    std::cout << std::fixed << std::setprecision(10); // Thiết lập hiển thị 10 chữ số thập phân

    double result1 = realSqrt(num1, iters);
    std::cout << "Can bac hai (BS) cua " << num1 << " la: " << result1 << std::endl;
    std::cout << "Can bac hai (std::sqrt) cua " << num1 << " la: " << std::sqrt(num1) << std::endl;
    // Output xap xi: 2.0000000000

    double num2 = 8.0;
    double result2 = realSqrt(num2, iters);
    std::cout << "Can bac hai (BS) cua " << num2 << " la: " << result2 << std::endl;
    std::cout << "Can bac hai (std::sqrt) cua " << num2 << " la: " << std::sqrt(num2) << std::endl;
     // Output xap xi: 2.8284271247

    double num3 = 0.5;
    double result3 = realSqrt(num3, iters);
    std::cout << "Can bac hai (BS) cua " << num3 << " la: " << result3 << std::endl;
    std::cout << "Can bac hai (std::sqrt) cua " << num3 << " la: " << std::sqrt(num3) << std::endl;
     // Output xap xi: 0.7071067812

    double num4 = 1000000.0;
    double result4 = realSqrt(num4, iters);
    std::cout << "Can bac hai (BS) cua " << num4 << " la: " << result4 << std::endl;
    std::cout << "Can bac hai (std::sqrt) cua " << num4 << " la: " << std::sqrt(num4) << std::endl;
     // Output xap xi: 1000.0000000000


    return 0;
}

Giải thích Code:

Hàm realSqrt nhận vào một số thực n và số lần lặp iterations.
Phạm vi tìm kiếm ban đầu [left, right] được thiết lập. Việc sử dụng std::max(1.0, n) là một cách để đảm bảo khoảng tìm kiếm đủ lớn cho cả trường hợp 0 <= n < 1 (khi đó căn bậc hai lớn hơn n) và n >= 1.
Vòng lặp for chạy số lần cố định thay vì điều kiện left <= right. Mỗi lần lặp giảm khoảng tìm kiếm đi một nửa. Sau 100 lần lặp, khoảng [left, right] sẽ cực kỳ nhỏ ($(right_{initial} - left_{initial}) / 2^{100}$), đảm bảo độ chính xác cao cho kiểu double.
mid = left + (right - left) / 2.0; tính điểm giữa. Chia cho 2.0 để đảm bảo phép tính trên số thực.
Kiểm tra mid * mid < n.
- Nếu đúng, mid quá nhỏ, căn thật nằm trong khoảng [mid, right]. Cập nhật left = mid.
- Nếu sai (tức là mid * mid >= n), mid quá lớn hoặc chính xác, căn thật nằm trong khoảng [left, mid]. Cập nhật right = mid.
- Lưu ý rằng mid luôn được giữ lại trong khoảng tìm kiếm mới (left = mid hoặc right = mid), khác với Binary Search trên số nguyên khi ta thường loại bỏ mid bằng cách cộng/trừ 1.
Sau vòng lặp, left (hoặc right, hoặc trung bình của chúng) là giá trị xấp xỉ căn bậc hai của n với độ chính xác cao.
Hàm main minh họa cách sử dụng, bao gồm cả việc thiết lập độ chính xác hiển thị cho double bằng std::fixed và std::setprecision.

Kỹ thuật Binary Search trên miền liên tục này rất hữu ích trong các bài toán tối ưu hóa khi bạn cần tìm một giá trị thực mà tại đó một hàm đơn điệu đạt giá trị mong muốn hoặc một tính chất nào đó thay đổi.

4. Những Lưu Ý Quan Trọng Khi Sử Dụng Binary Search

Áp dụng Binary Search hiệu quả đòi hỏi sự cẩn trọng, đặc biệt là ở các ranh giới và điều kiện dừng. Dưới đây là một số điểm cần ghi nhớ:

Dữ liệu/Tính chất phải có tính đơn điệu: Đây là điều kiện tiên quyết. Dữ liệu phải được sắp xếp (đối với mảng) hoặc tính chất bạn kiểm tra phải tạo ra ranh giới rõ ràng chia không gian tìm kiếm thành hai phần: một phần thỏa mãn và một phần không thỏa mãn (hoặc ngược lại).
Xác định rõ không gian tìm kiếm: Biến left và right của bạn đại diện cho cái gì? Chỉ số mảng? Giá trị nguyên? Giá trị thực? Phạm vi ban đầu của chúng là bao nhiêu? Khoảng này là đóng [left, right] hay mở (left, right) hay nửa mở/nửa đóng? Hãy nhất quán.
Kiểm tra điều kiện tại mid: Điều kiện này là gì? Khi nào thì mid nằm ở "phía nhỏ hơn" và khi nào nằm ở "phía lớn hơn" so với đáp án cần tìm?
Cập nhật left và right: Đây là nơi dễ xảy ra lỗi "off-by-one" hoặc vòng lặp vô tận.
- Nếu mid không thể là đáp án, bạn nên loại bỏ nó khỏi khoảng tìm kiếm tiếp theo: left = mid + 1 hoặc right = mid - 1. (Thường dùng trong tìm kiếm giá trị cụ thể trên mảng).
- Nếu mid có thể là đáp án (ví dụ: bạn đang tìm ranh giới, và mid nằm ở phía "thỏa mãn" ranh giới), bạn cần giữ mid trong khoảng tìm kiếm mới: left = mid hoặc right = mid. (Thường dùng trong tìm kiếm ranh giới, tìm kiếm trên miền giá trị, hoặc Binary Search trên số thực).
- Việc lựa chọn left = mid + 1 vs left = mid và right = mid - 1 vs right = mid phụ thuộc vào chính xác bài toán bạn đang giải (tìm giá trị, tìm ranh giới đầu tiên, tìm ranh giới cuối cùng, v.v.) và cách bạn định nghĩa khoảng tìm kiếm [left, right).
Điều kiện dừng của vòng lặp:
- Với số nguyên: while (left <= right) cho khoảng đóng [left, right] là phổ biến.
- Với số thực: Lặp cố định số lần là phương pháp đơn giản và hiệu quả để đạt độ chính xác mong muốn.
Nguy cơ tràn số: Luôn cẩn trọng khi tính mid = left + (right - left) / 2 và khi kiểm tra các điều kiện liên quan đến bình phương hoặc các phép tính khác trên mid, đặc biệt với các bài toán trên miền giá trị nguyên lớn. Sử dụng long long khi cần thiết.

Bài tập ví dụ:

Tìm Mex

Trong một buổi thảo luận về ứng dụng di động mới, FullHouse Dev đã nhận được một thử thách thú vị từ một nhà phát triển điện thoại thông minh. Họ được yêu cầu tạo ra một thuật toán để tính giá trị Mex cho một dãy số, như một phần của tính năng bảo mật mới cho ứng dụng. Với niềm đam mê công nghệ và tinh thần đổi mới, FullHouse Dev đã quyết định giải quyết bài toán này.

Bài toán

Cho một mảng số nguyên có độ dài $n$. Nhiệm vụ của FullHouse Dev là tìm giá trị Mex cho mỗi phần tử thứ $i$ trong mảng $(1 \leq i \leq n)$.

Mex của phần tử thứ $i$ là số nguyên không âm nhỏ nhất lớn hơn hoặc bằng $0$ mà không xuất hiện trong mảng từ chỉ số $1$ đến $i$.

INPUT FORMAT:

Dòng đầu tiên chứa một số nguyên $n$ - độ dài của mảng.
Dòng thứ hai chứa $n$ số nguyên - các phần tử của mảng.

OUTPUT FORMAT:

In ra $n$ số nguyên. Số thứ $i$ là giá trị Mex của mảng con từ phần tử đầu tiên đến phần tử thứ $i$.

Ràng buộc:

$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^9$ (các phần tử trong mảng)

Ví dụ

INPUT

5
1 0 5 5 3

OUTPUT

0 2 2 2 2

Giải thích

Mex của phần tử đầu tiên là 0, vì 0 không có trong mảng.
Mex của hai phần tử đầu tiên là 2, vì 0 và 1 đã có trong mảng.
Mex của ba, bốn và năm phần tử đầu tiên vẫn là 2, vì 0 và 1 vẫn là các số nhỏ nhất không có trong mảng con tương ứng.

FullHouse Dev đã giải quyết thành công bài toán này, chứng minh khả năng xử lý các vấn đề thuật toán phức tạp và sẵn sàng áp dụng vào việc phát triển các tính năng bảo mật tiên tiến cho ứng dụng di động. Hướng dẫn giải bài Tìm Mex:

Ý tưởng chính: Duyệt qua mảng từ trái sang phải, lần lượt xét từng tiền tố (prefix) của mảng. Đối với mỗi tiền tố a[1...i], ta cần tìm số nguyên không âm nhỏ nhất chưa xuất hiện trong tiền tố đó.
Theo dõi các số đã xuất hiện: Khi ta mở rộng tiền tố từ a[1...i] sang a[1...i+1] bằng cách thêm phần tử a[i+1], tập hợp các số đã xuất hiện chỉ có thêm một phần tử mới (a[i+1]). Điều này có nghĩa là giá trị Mex cho tiền tố a[1...i+1] sẽ lớn hơn hoặc bằng giá trị Mex của tiền tố a[1...i]. Nó không bao giờ giảm.
Cập nhật Mex hiệu quả:
- Khởi tạo giá trị Mex hiện tại là 0.
- Sử dụng một cấu trúc dữ liệu để lưu trữ các số nguyên không âm đã xuất hiện trong tiền tố hiện tại. Một set (tập hợp) hoặc một mảng đánh dấu tần suất (nếu các giá trị nhỏ) là phù hợp. Do giá trị a_i có thể rất lớn (nhưng Mex không vượt quá n), một set là lựa chọn tốt để lưu các số a_i thực tế đã thấy.
- Duyệt qua mảng từ phần tử đầu tiên đến cuối cùng.
- Tại bước thứ i (khi xử lý phần tử a[i]), thêm a[i] vào cấu trúc dữ liệu lưu trữ các số đã xuất hiện.
- Kiểm tra xem giá trị Mex hiện tại có nằm trong cấu trúc dữ liệu đó không. Nếu có, tăng giá trị Mex hiện tại lên 1 và lặp lại việc kiểm tra cho đến khi gặp một số không có trong cấu trúc dữ liệu.
- Giá trị Mex hiện tại sau khi cập nhật chính là Mex cho tiền tố a[1...i]. In giá trị này ra.
Cấu trúc dữ liệu: Một std::set<int> trong C++ là lựa chọn tốt cho việc lưu trữ các số đã xuất hiện, vì nó hỗ trợ thêm (insert) và kiểm tra sự tồn tại (count/find) hiệu quả (thường là O(log N)).
Độ phức tạp:
- Thời gian: Mỗi phần tử của mảng được thêm vào set một lần (O(log N) cho mỗi lần thêm). Giá trị Mex hiện tại chỉ tăng và tối đa là n. Tổng số lần tăng Mex trên toàn bộ quá trình duyệt là O(N). Mỗi lần kiểm tra trong vòng lặp cập nhật Mex là O(log N) trên set. Tổng thời gian là khoảng O(N log N).
- Không gian: O(N) để lưu trữ các số đã xuất hiện trong set (tối đa N số khác nhau).
Triển khai (gợi ý):
- Đọc N.
- Khởi tạo std::set<int> seen_numbers;.
- Khởi tạo int current_mex = 0;.
- Vòng lặp N lần:
  - Đọc số tiếp theo a_i.
  - Thêm a_i vào seen_numbers.
  - Sử dụng vòng while để kiểm tra seen_numbers.count(current_mex) và tăng current_mex cho đến khi nó không còn trong set.
  - In current_mex.

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

Comments

There are no comments at the moment.