BINARY SEARCH

Binary Search là kĩ thuật rất quen thuộc, có ứng dụng nhiều. Nhắc tới Binary Search, ai cũng nghĩ ngay đến "có một dãy số đã sort, để tìm một phần tử nào trong dãy thì chia dãy làm hai phần, rồi so sánh phần tử cần tìm với phần tử ngay giữa, còn nhiều xử lí nữa ..., quan trọng là ta tìm kiếm được phần tử trong dãy trong thời gian log(n), với n là kích thước của dãy". Có phải bạn cũng nghĩ như vậy? Uh, bạn hiểu đúng rồi đó. Hầu hết các ngôn ngữ lập trình phổ biến có hỗ trợ sort và search, nên đôi khi ta ít trực tiếp viết code binary search. Thật sự binary search được dùng khá nhiều hơn là ta thường nghĩ. Ứng dụng của binary search thì khá nhiều, mình đưa ra hai trường hợp sau để bạn hiểu rõ hơn về binary search.

1. Binary search và bài toán tối ưu

Bài toán tối ưu: có nhiều phương án cho một vấn đề, nhiệm vụ là phải chọn ra một phương án tốt nhất dựa trên một tiêu chí nào đó.

Ta xét ví dụ sau đây:

Ví dụ: Bạn muốn mua N (N<=10^5) món hàng trong một cửa hàng. Mỗi món hàng có giá trị là Vi (1<=i<=N, 1<=Vi <= 10^6 VND). Cửa hàng đang có đợt khuyến mãi đặc biệt, chủ cửa hàng cho bạn trả giá với cách sau: Bạn đưa ra một số M, tất cả các món hàng nào có giá lớn hơn M thì bạn được quyền mua với giá là M, ngược lại thì bạn có thể mua với giá đúng giá trị của nó.

Chẳng hạn cửa hàng có 3 món hàng trị giá 30, 50 ,90. Nếu bạn trả giá với M=60, thì bạn sẽ mua 3 món hàng này với giá 30, 50, 60.

Dĩ nhiên là có điều kiện ràng buộc rồi: sau khi bạn đưa ra M, thì tổng giá tiền mà bạn phải trả phải lớn hơn hoặc bằng S, 0<=S<=(tổng các Vi). Ví dụ như trường hợp vừa nêu, nếu chủ cửa hàng yêu cầu S=140, thì bạn không thể đưa ra giá M = 59.

Nhiệm vụ của mình là dựa vào các giá trị V1, V2, ..., VN và S để tìm ra M tối ưu, tức là số tiền phải trả là nhỏ nhất.

Phân tích: Dĩ nhiên là ta cần tìm M càng nhỏ càng tốt sao cho thỏa mãn điều kiện của cửa hàng. Với yêu cầu của cửa hàng, ta có thể chạy qua từng giá trị của M từ 1 đến giá trị lớn nhất, nếu giá trị nào M thỏa yêu cầu thì ta ngừng và đó chính là kết quả mà ta cần tìm. Tuy nhiên với cách làm này thì trong trường hợp xấu nhất ta phải mất O(10^6*N) để tìm ra M. Con số này không thể chấp nhận được với các máy tính thông thường để tìm ra kết quả trong vài giây.

Ta có một số nhận xét sau:

+ Nếu M = M0 không thỏa yêu cầu, thì (M0-1) cũng sẽ không thỏa yêu cầu, từ đây suy ra tất cả M nhỏ hơn M0 đều ko thỏa (bạn tự chứng minh, dùng phản chứng) (*)

+ Nhận xét trên tương đương với, nếu M = M0 thỏa yêu cầu, thì (M0+1) cũng thỏa yêu cầu (bạn tự chứng minh)

+ M = max(Vi) luôn thỏa yêu cầu vì S<=(tổng các Vi)

Từ những nhận xét này ta suy ra nhận xét tiếp theo:

Gọi M' là kết quả cần tìm, tức là M’ là số nhỏ nhất thỏa.

       + Nếu M=M0 thỏa yêu cầu, thì M'<=M0 (vì M' là nhỏ nhất).

       + Nếu M=M0 không thỏa yêu cầu, thì M'>M0 vì theo nhận xét (*).

Tới đây ta có thể suy luận ra để giải quyết bài toán:

Với cách này, chương trình của mình sẽ chạy trong log(10^6)*N = 20*N

Code được viết bằng C++ tại https://www.dropbox.com/s/ajz5xsrgsxrilm3/Buying.cpp . Bạn chú ý khi dùng binary search trên số nguyên, cần thận với việc làm tròn số nguyên, ví dụ nếu left=2, right=3. Nếu ko cẩn thận sẽ bị lặp vô tận trong vòng lặp.

Đó chính là ý tưởng binary search. Để tìm một phần tử x trong tập hợp A thỏa điều kiện nào đó. Ta chia A thành hai tập A1, và A2 có số phần tử gần bằng nhau. Sau đó xác định x thuộc A1 hoặc A2. Loại bỏ một tập và tiếp tục quá trình này cho đến khi tìm được x hoặc xác định x không thuộc tập A. Còn về thời gian để tìm ra phần tử x, ta dễ dàng tính được log(n)*(thời gian để xác định x thuộc một trong A1 hoặc A2), với n = |A|.

Ta tìm lời giải tối ưu (nhỏ nhất hoặc lớn nhất) cho một bài toán. Bài toán có dạng:

Tìm M nhỏ nhất (lớn nhất) sao cho hàm Check(M) là true. Check() chính là yêu cầu bài toán. Để áp dụng được binary search thì phải thỏa điều kiện sau: nếu Check(M0) là false thì Check(M) là false với mọi M<=M0 hoặc phát biểu tương đương nếu Check(M0) là true thì Check(M) là true với mọi M>=M0.

2. Binary search và kĩ thuật phân tập

Một kĩ thuật cũng khá hay khi áp dụng binary search, đó là kĩ thuật phân tập.

Ví dụ: cho một tập S có N phần tử {a1, a2, a3,… aN}, bạn hãy kiểm tra có tồn tại tập con của S thỏa mãn tổng các phần tử của tập con đó là K. (N<=30)

Cách giải: đây là bài toán NP, vì thế ta phải duyệt qua tất cả các tập con để tìm ra kết quả. Nếu duyệt qua bình thường thì ta tốn thời gian 2^N, con số này cũng khá cao không thể duyệt qua hết nỗi.

Độ phức tạp: tập S có 2^N tập con => độ phức tạp 2^N khoảng 10⁹ , thời gian chạy này không thể cho phép được.

Cải tiến: Ta chia tập S thành 2 tập S1 = {a1, a2, …, aN/2} và S2={aN/2+1, aN/2+2,…, aN} hai tập này có số phần tử bằng nhau, nếu N lẻ thì S2 nhiều hơn 1 phần tử, ta liệt kê tất cả các tập con của S1, S2; sau đó sort lại các tập con của S2 theo thứ tự tăng dần theo giá trị tổng các phần tử của tập con đó. Ứng với mỗi tập con của S1 (giả sử tập con này là A có tổng là K1) ta dùng binary search để tìm ra tập con tương ứng của S2 có tổng là K-K1 (gọi tập con này là B). Lúc này ta có một tập con C = A U B của S thỏa tổng các phần tử là K. Cứ duyệt qua hết tập con S1 là ta có đáp án.

Độ phức tạp: Sinh S1, S2 mất 2*2^(N/2), mỗi tập con của S1, ta tìm một tập con của S2, thao tác này mất chi phí : 2^(N/2)*log₂(2^(N/2)) = N/2*2^(N/2)

=>  O(N/2*2^(N/2)) = 10⁶, chạy 1s là Ok.

Nhận xét:

1. Với cách làm này thì ta có thể giải cho các trường hợp N<=30, nếu N lớn hơn cũng không khả thi vì bản chất bài này vẫn là NP.
2. Việc sinh tập S1, S2 ta có thể vận dụng từ bài viết BITMASKS.

Bạn có thể xem code C++ tại https://www.dropbox.com/s/ikct96n7hnpep89/SubSet.cpp, code này tìm ra tất cả các tập con thỏa tổng của các phần tử bằng K.

Các bài toán áp dụng kĩ thuật phân tập: 

http://vn.spoj.pl/problems/LQDDIV/

https://vn.spoj.pl/problems/VECTOR/

https://vn.spoj.pl/problems/COIN34/

http://vn.spoj.pl/problems/CHNREST/

Tổng kết:
Binary search thường được sử dụng khá nhiều, nhưng nó hay được dùng  kết hợp với những kỹ thuật để giải quyết vấn đề. Bạn có thể luyện skill về binary search tại http://codeforces.com/problemset/tags/binary%20search

Người viết: Dương Thành Phong