Chặt nhị phân và các biến thể – part 1

Prob 1: Cho mảng a tăng dần, tìm vị trí của phần tử có giá trị bằng key

int bsearch( int * a, int lo, int hi, int key ) {
while(lo <= hi) {
        int mi = (lo + hi) / 2;
        if (a[mi] == key) return mi;
        else if (a[mi] < key) lo = mi + 1;
        else hi = mi - 1;
    }
    
    return -1;
}

Nhận xét: Nếu tìm thấy x, thì:
+ lo sẽ là vị trí của phần tử nhỏ nhất, đầu tiên lớn hơn key trong mảng
+ hi sẽ là vị trí của phần tử lớn nhất, cuối cùng bé hơn key trong mảng
( tất nhiên lo và hi phải thuộc đoạn chỉ số mà chúng ta đang tìm kiếm )
=> Chặt nhị phân tiến sát đến 2 phần tử “kẹp giữa” giá trị key trong dãy.

Tính chất này khá thú vị nhưng khó ứng dụng vì nó chỉ đúng khi key được tìm thấy. Ta đến với Prob 2, 3 như sau:

Prob 2: Cho mảng a tăng dần, tìm vị trí của phần tử đầu tiên có giá trị nhỏ nhất mà lớn hơn hoặc bằng key

int bsearch( int * a, int lo, int hi, int key ) {
    
    int ans = -1;
    
    while(lo <= hi) {
        int mi = (lo + hi) / 2;
        if (a[mi] >= key) { // neu a[mi] thoa man dk
            ans = mi;       // luu ket qua vao ans
            hi = mi - 1;    // thu nho pham vi tim kiem
        } else lo = mi + 1;
    }
    
    return ans;
}

Nhận xét: Nếu muốn tìm vị trí của phần tử đầu tiên lớn hơn key, chỉ cần thay điều kiện thoả mãn thành a[mi] > key

Prob 3: Cho mảng a tăng dần, tìm vị trí của phần tử cuối cùng có giá trị lớn nhất mà nhỏ hơn hoặc bằng key

int bsearch( int * a, int lo, int hi, int key ) {
    
    int ans = -1;
    
    while(lo <= hi) {
        int mi = (lo + hi) / 2;
        if (a[mi] <= key) { // neu a[mi] thoa man dk
            ans = mi;       // luu ket qua vao ans
            lo = mi + 1;    // thu nho pham vi tim kiem
        } else hi = mi - 1;
    }
    
    return ans;
}

Nhận xét: Nếu muốn tìm vị trí của phần tử đầu tiên nhỏ hơn x, thay điều kiện thoả mãn thành a[mi] < key

Prob 4: Cho dãy số nguyên không âm a, vị trí s và số nguyên distance. Tìm vị trí t < s sao cho a[t] + a[t+1]… + a[s] <= distance, và t nhỏ nhất có thể.

Giả sử đã quy hoạch động được mảng f[i] = a[1] + a[2] +… + a[i]. Tiến hành chặt nhị phân như sau:

int bsearch( int * a, int s, int distance)
{
int lo = 0;
int hi = s – 1;
int ans = -1;

while(lo <= hi) {
int t = (lo + hi) / 2;
if (f[s] – f[t] + a[t] <= distance) { // dieu kien thoa man
ans = t; // luu ket que
hi = t – 1; // thu nho pham vi tim kiem
} else lo = t + 1;
}

return ans;
}

Ứng dụng: http://vn.spoj.com/problems/QBTICKET/
Dựa vào Prob 3, làm tương tự cho Prob 4 với trường hợp t > x và t lớn nhất có thể

Kết bài: ở 3 Problem cuổi, mình hoàn toàn code phân xử lí nhị phân ( vòng while) giống nhau, đều dựa trên 3 phần: điều kiện để thoả mãn bài toán, lưu kết quả, và thu nhỏ phạm vi tìm kiếm cho phù hợp. Việc phân rạch ròi 3 phần giúp mình hiểu rõ hơn về tìm kiếm nhị phân, cũng như dễ dàng vận dụng nó cho những điều kiện khác nhau. Hi vọng có thể giúp các bạn

Happy codding 🙂

Advertisements

One thought on “Chặt nhị phân và các biến thể – part 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s