08. Parallel Binary Search

Bài toán mở đầu

Cho một mảng A có N phần tử a_0, a_1, ...a_{N-1} (các phần tử được cho theo thứ tự không giảm về giá trị) và một mảng X có M phần tử x1, x2, ..., xM. Nhiệm vụ của chúng ta là: với ,mỗi phần tử xi, tìm chỉ số của phần tử cuối cùng trong A còn nhỏ hơn hoặc bằng xi.

Ví dụ: 

Input:

A [1, 2, 2, 6, 7, 7, 8, 11, 15]

X [7, 2, 13, 9]

Output:

5 2 7 6

Cách làm đơn giản nhất chúng ta có thể thấy được là với mỗi phần tử của x ta thực hiện tìm kiếm nhị phân trên A. Quá trình có thể quan sát trực quan như sau:

Độ phức tạp: O(M*logN)

Với độ phức tạp này, chúng ta dễ thấy cũng tạm chấp nhận được. Tuy nhiên, ở đây giá trị mảng A được cho sẵn nên nên chúng ta chỉ việc tìm kiếm nhị phân trên đó. Trong nhiều bài toán phức tạp, các giá trị mảng A thường không có sẵn mà phải thực hiện nhiều thao tác tính toán, thậm chí duyệt trên một vùng dữ liệu lớn mới lấy được kết quả vào một ô của mảng. 

Quan sát lại quá trình tính toán ở bảng trên, chúng ta thấy thao tác đầu tiên của cả truy vấn xi (i =1 ..4) đều chọn mid tại vị trí 4 (và vùng tìm kiếm từ L =0 đến R = 8). Sau đó đó các xi sẽ được đi về hai phía khác nhau của Mid, và cứ như vậy cho các bước sau. Như vậy dễ thấy rằng khi dữ liệu nới rộng,  với mỗi lần chúng ta chia vùng tìm kiếm làm đôi, có rất nhiều xi sẽ cùng thuộc vùng này hoặc vùng kia.

Như vậy thay vì thực hiện tìm kiếm nhị phân cho từng xi, chúng ta sẽ thực hiện tìm nhị phân trên từng vùng, mỗi vùng này chứa một tập hợp các xi cần xử lý, ta lại chọn mid của mỗi vùng tương ứng với số lượng ứng viên của nó rồi lại chia vùng trên đó. Đây chính là ý tưởng của chặt nhị phân song song, tức là chúng ta đi tìm kiếm nhị phân dựa trên những vùng được chia nhị phân.

Tài liệu tham khảo

Codefore

CP algorithm

VNOI Wiki

Ý tưởng chính

Như vậy, chúng ta thay đổi hướng nhìn so với chặt nhị phân thông thường, thay vì thực hiện lại việc chặt nhị phân cho từng truy vấn (vị trí của xi trong trường hợp này), chúng ta sẽ xác định xem một vùng tìm kiếm [L, R) có thể trả lời được cho bao nhiêu truy vấn.