Editorial for search3: Tìm kiếm nhị phân 3

Hiểu bài toán

Cho hai dãy số nguyên A (kích thước n) và B (kích thước m). Với mỗi phần tử bi trong dãy B, nhiệm vụ tìm ra chỉ số j nhỏ nhất (1-based) trong dãy A sao cho aj = bi. Nếu bi không xuất hiện trong A, output là 0. Nhập xuất dữ liệu lên tới 10^5 phần tử và giá trị số có thể lên tới 10^9.

Các cách tiếp cận

Cách Binary Search (Sắp xếp + Tìm kiếm nhị phân)

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int val;
    int pos;
} Pair;

int cmp(const void *a, const void *b) {
    Pair *x = (Pair*)a;
    Pair *y = (Pair*)b;
    if (x->val != y->val) return x->val - y->val;
    return x->pos - y->pos;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    Pair *pairs = (Pair*)malloc(n * sizeof(Pair));
    for (int i = 0; i < n; i++) {
        scanf("%d", &pairs[i].val);
        pairs[i].pos = i + 1;
    }
    qsort(pairs, n, sizeof(Pair), cmp);

    for (int i = 0; i < m; i++) {
        int b;
        scanf("%d", &b);
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (pairs[mid].val == b) {
                ans = pairs[mid].pos;
                r = mid - 1; // Tìm tiếp về bên trái để lấy index nhỏ nhất
            } else if (pairs[mid].val < b) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        printf("%d ", ans);
    }
    free(pairs);
    return 0;
}

• Time Complexity: O(n log n + m log n)
• Space Complexity: O(n)

Cách tiếp cận này tối ưu hóa việc tìm kiếm bằng cách sắp xếp mảng A cùng với chỉ số gốc của từng phần tử. Sau đó, với mỗi truy vấn từ B, ta sử dụng tìm kiếm nhị phân (binary search) để kiểm tra sự tồn tại và tìm chỉ số nhỏ nhất.

1. Tạo mảng cấu trúc (struct) lưu giá trị và chỉ số (1-based) của A.
2. Sắp xếp mảng này theo giá trị tăng dần; nếu giá trị bằng nhau thì sắp xếp theo chỉ số tăng dần.
3. Với mỗi giá trị bi, dùng binary search để tìm phần tử đầu tiên có giá trị bằng bi.
4. Nếu tìm thấy, in ra chỉ số lưu trong cấu trúc; ngược lại in 0.

Độ phức tạp: Sắp xếp O(n log n), tìm kiếm O(m log n).

Cách Hash Map (Mảng băm)

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

int main() {
    int n, m;
    cin >> n >> m;
    unordered_map<int, int> first_pos;

    // Đọc mảng A và lưu chỉ số xuất hiện đầu tiên
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        // Chỉ ghi nhận nếu chưa tồn tại (đảm bảo lấy index nhỏ nhất)
        if (first_pos.find(a) == first_pos.end()) {
            first_pos[a] = i;
        }
    }

    // Xử lý truy vấn từ B
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        auto it = first_pos.find(b);
        if (it != first_pos.end()) {
            cout << it->second << " ";
        } else {
            cout << "0 ";
        }
    }
    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Sử dụng cấu trúc dữ liệu Hash Map (hoặc map trong C++) để lưu trữ các cặp (giá trị, chỉ số) của dãy A.

1. Duyệt qua dãy A từ đầu (i từ 1 đến n). Nếu giá trị ai chưa có trong map, thêm (ai, i) vào map.
2. Khi duyệt từ đầu, chỉ số i đầu tiên được lưu lại chính là chỉ số nhỏ nhất.
3. Với mỗi giá trị b_i trong B, chỉ cần tra cứu trong map. Nếu có thì trả về giá trị, ngược lại trả về 0.

Đây là phương pháp hiệu quả nhất về thời gian truy vấn, nhưng tốn bộ nhớ hơn.

Cách Brute Force (Duyệt tuần tự)

#include <stdio.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int a[100005];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < m; i++) {
        int b;
        scanf("%d", &b);
        int found = 0;
        // Duyệt từ đầu để tìm index nhỏ nhất
        for (int j = 0; j < n; j++) {
            if (a[j] == b) {
                printf("%d ", j + 1);
                found = 1;
                break;
            }
        }
        if (!found) printf("0 ");
    }
    return 0;
}

• Time Complexity: O(n * m) ~ 10^10 thao tác
• Space Complexity: O(n)

Phương pháp ngây thơ nhất. Với mỗi phần tử trong B, ta duyệt qua toàn bộ mảng A để tìm giá trị đó.

1. Đọc toàn bộ mảng A vào bộ nhớ.
2. Với mỗi phần tử bi của B:
   • Duyệt j từ 0 đến n-1.
   • Nếu a[j] == bi, in j+1 và dừng vòng lặp (để lấy index nhỏ nhất).
   • Nếu duyệt hết mà không thấy, in 0.

Phù hợp với dữ liệu nhỏ, nhưng chắc chắn bị TLE (Time Limit Exceeded) với n, m lên tới 10^5.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Để tìm chỉ số nhỏ nhất, khi sắp xếp ta cần giữ lại chỉ số ban đầu và dùng comparator thứ cấp để sắp xếp theo chỉ số nếu giá trị bằng nhau.
• Binary Search là giải pháp cân bằng giữa thời gian và bộ nhớ, trong khi Hash Map tối ưu hóa hoàn toàn thời gian truy vấn.

Lỗi thường gặp

• Lỗi Indexing: Đầu vào yêu cầu index 1-based, nhưng lập trình C/C++ thường dùng 0-based, cần cộng thêm 1 khi in ra.
• Lỗi Logic Binary Search: Khi tìm thấy giá trị, không được dừng lại ngay mà phải tiếp tục tìm về bên trái (r = mid - 1) để đảm bảo tìm được phần tử đầu tiên (index nhỏ nhất).