[kĩ năng cần biết] tìm kiếm nhị phân (chặt nhị phân)

thienvamai · 20 Tháng tám 2013

Bài viết được lấy từ blog của coder Nguyễn Tiền Trung Kiên (kiencoi1997) , mọi sao chép phải được sự đồng ý của chủ nhân bài viết.

Chặt nhị phân
Để tìm kiếm một phần tử trong mảng. Với cách thông thường, ta phải duyệt tất cả các số từ a[1] đến a[n], tức là mất độ phức tạp O(n). Tuy nhiên với mảng đơn điệu (dãy không tăng hoặc không giảm), thì ta chỉ mất độ phức tạp O(logn) để tìm kiếm, với bài toán này, ta dùng chặt nhị phân để tìm kiếm. Bài viết này tôi sẽ viết về cách chặt nhị phân và chặt tam phân.
Lưu ý:
- Chặt nhị phân chỉ dùng đưuọc cho dãy đơn điệu
- Chặt tam phân chỉ dùng được cho dãy tăng rồi giảm (hoặc giảm rồi tăng), tức là tồn tại một điểm i mà a[1..i] đơn điệu, a[i..n] đơn điệu.
- Có rất nhiều cách chặt nhị phân, và mỗi người lại code một cách khác nhau. Ở đây tôi xin đưuọc trình bày cách mà tôi thương dùng, vì cách này có tương đối nhiều ưu điểm.

1. Chặt nhị phân trên mảng
Giả sử ta có bài toán sau:
Cho một dãy n số. Với mỗi số k được nhập vào, in ra một số nằm trong dãy ban đầu, nhỏ nhất và lớn hơn hoặc bằng số k. (Sẽ có Q số k được nhập, Q<=100000, n<=100000)
Trước hết ta thấy rằng có thể sort lại mảng a (gọi a là dãy số ban đầu). Vì vậy ta có thể giả sử a là dãy không giảm. Ta sẽ làm như sau:

Mã:

sort(a);
left=1, right=n;
for i = left to right do
if a[i]>=k then return a[i];
print "Not found"

Dưới đây là code không dùng chặt nhị phân.

PHP:

Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;

int n, k, m;
int a[1230997];

void bsearch(int k){
    int ll=1, rr=n, i;
    for (i=ll; i<=rr; i++)
    if (a[i]>=k) { printf("%d\n", a[i]); return; }
    printf("Not found\n");
}

main(){
    int i;
    scanf("%d", &n);
    for (i=1; i<=n; i++) scanf("%d", &a[i]);
    sort(a+1, a+n+1);
    scanf("%d", &m);
    for (i=1; i<=m; i++){
        scanf("%d", &k);
        bsearch(k);
    }
}

Với thuật toán như trên, độ phức tạp là O(mn) (với m là số truy vấn/câu hỏi). Tôi sẽ thêm một số lệnh để giảm độ phức tạp xuống O((m+n) logn). Các lệnh mà tôi thêm vào sẽ được tô màu đỏ.

Mã:

sort(a);
left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>=k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = left to right do
if a[i]>=k then return a[i];
print "Not found"

PHP:

Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;

int n, k, m;
int a[1230997];

void bsearch(int k){
    int ll=1, rr=n, i=(ll+rr)/2;

    while (ll!=i && i!=rr){
        if (a[i]>=k) rr=i;
        else ll=i;
        i=(ll+rr)/2;
    }

    for (i=ll; i<=rr; i++)
    if (a[i]>=k) { printf("%d\n", a[i]); return; }
    printf("Not found\n");
}

main(){
    int i;
    scanf("%d", &n);
    for (i=1; i<=n; i++) scanf("%d", &a[i]);
    sort(a+1, a+n+1);
    scanf("%d", &m);
    for (i=1; i<=m; i++){
        scanf("%d", &k);
        bsearch(k);
    }
}

Với cách làm này, ta có thể kiểm tra độ chính xác của thuật toán bằng hàm bsearch ban đầu. Sau đó bạn có thể thêm một số dòng lệnh để cho chương trình chạy nhanh hơn.
Code trên đảm bảo rằng, với các a giống nhau, hàm sẽ trả về a đầu tiên trong mảng, để rõ hơn về điều này, ta xét bài toán sau.
Cho một dãy a đã sắp xếp tăng dần. Lần lượt nhập m số k. Có hai bài toán:
a, Với mỗi k, in ra số đầu tiên bé nhất lơn hơn hoặc bằng k.
b, Với mỗi k, in ra số cuối cùng lớn nhất bé hơn hoặc bằng k.
Tức là ở bài toán a, trong các a thỏa mãn và bằng nhau, chọn a có i nhỏ nhất. Ở bài toán b, trong các a thỏa mãn và bằng nhau, chọn a có i lớn nhất.

Trở lại với cách làm ở trên, đây là nội dung mã giả ở trên

Mã:

sort(a); left=1, right=n; i = (left + right) / 2; while (left != i) and (i != right) do if a[i]>=k then right = i; else left = i; i = (left + right) / 2; for i = left to right do if a[i]>=k then return a[i]; print "Not found"

Để ý rằng dòng tô đỏ (if a>k ...) ở trên, sẽ gán right = i cả khi a = k. Vì thế kết quả luôn là a với i nhỏ nhất. Để chọn i lớn nhất, ta thay đổi hai dòng tô đỏ ở trên thành:

Mã:

sort(a); left=1, right=n; i = (left + right) / 2; while (left != i) and (i != right) do if a[i]>k then right = i; else left = i; i = (left + right) / 2; for i = right to left do if a[i]<=k then return a[i]; print "Not found"

2. Chặt nhị phân trên hàm
Với các hàm số thực, ta cũng làm tương tự như chặt nhị phân trên mảng. Giả sử ta có bài toán sau:
Nhập một số thực nằm trong khoảng từ 0 đến 1 (0 <= key <= 1). Tìm x để sin x = key.
Với bài này, ta đặt left=0, right =pi/2, sau đó chặt nhị phân giống như thuạt toán bên trên:

Mã:

left=0, right=PI/2; i = (left + right) / 2; while (left != i) and (i != right) do if sin(i)>=key then right = i; else left = i; i = (left + right) / 2; print (l+r)/2;

Thuật toán như trên chắc chắn sẽ dừng tại một lúc nào đó, khi mà left rất gần với right, i sẽ bằng một trong hai giá trị left hoặc right, và lệnh while sẽ dừng lại. Bởi vậy, cách code ở trên không cần dùng epsilon, đây là một cách chặt nhị phân khá hay giúp bạn không cần phải quan tâm đến epsilon.

PHP:

Code này của Nguyễn Tiến Trung Kiên #include <stdio.h> #include <math.h> double bsearch(double key){ double ll=0, rr=M_PI/2, i=(ll+rr)/2; while (ll!=i && i!=rr){ if (sin(i) >= key) rr=i; else ll=i; i=(ll+rr)/2; } return (ll+rr)/2; } double key; main(){ scanf("%lf", &key); // 0 <= key <= 1 printf("answer = %lf\n", bsearch(key)); printf("arcsin = %lf\n", asin(key)); }

3. Chặt tam phân
Có những hàm không thể chặt nhị phân mà có thể chặt tam phân. Ví dụ : Cho hai điểm A, B trên mặt phẳng. Chọn một điểm C nằm trên trục Ox. Tìm điểm C để tổng AC + BC là nhỏ nhất. Gọi f(x) là tổng AC + BC với C ở tọa độ (x, 0). Ta cần tìm f(x) bé nhất.
Giả sử ta đã tìm đưuọc một điểm C0 thỏa mãn đề bài. Xét các điểm C nằm bên phải C0, ta tháy rằng khoảng cách từ C đến C0 càng tăng. Tương tự vơi bên trái. Có nghĩa là: bên phải điểm C0 là hàm tăng, bên trái C0 là hàm giảm, bới vậy ta dùng chặt tam phân.

Mã:

LL=minX, RR=maxX; ML=(LL+LL+RR)/3, MR=(LL+RR+RR)/3; while (LL!=ML) and (ML!=MR) and (MR!=RR) do if f(ML)>f(MR) then LL=ML; else RR=MR: ML=(LL+LL+RR)/3, MR=(LL+RR+RR)/3; print (LL+RR)/2;

Dòng chữ đỏ đâu tiên, có nghĩa là chia đoạn LL..RR thành ba khoảng: LL..ML, ML..MR, MR..RR. Dòng chữ đỏ thứ hai có nghĩa là: nếu f(ML) > f(MR) thì tất cả f(LL)..f(ML) đều lớn hơn f(MR) suy ra cả đoạn LL..ML đều không phải là đáp án của mình. Tương tự với trường hợp f(ML) < f(MR). Vì vậy thuật toán trên là đúng.

PHP:

Code này của Nguyễn Tiến Trung Kiên #include <stdio.h> #include <algorithm> #include <math.h> using namespace std; double xa, ya, xb, yb; double f(double x){ double AC = sqrt((xa-x)*(xa-x) + ya*ya); double BC = sqrt((xb-x)*(xb-x) + yb*yb); return AC+BC; } main(){ scanf("%lf%lf%lf%lf", &xa, &ya, &xb, &yb); double rr=max(xa, xb); double ll=min(xa, xb); double ml=(ll+ll+rr)/3; double mr=(ll+rr+rr)/3; while (ll!=ml && ml!=mr && mr!=rr){ if (f(ml) > f(mr)) ll=ml; else rr=mr; ml=(ll+ll+rr)/3; mr=(ll+rr+rr)/3; } printf("answer = %lf\n", (ll+rr)/2); printf("cost = %lf\n", f((ll+rr)/2)); }

4. Dùng thư viện có sẵn
Dưới đây là các hàm có sẵn trong thư viện algorithm và ví dụ về cách sử dụng. Các hàm này chỉ hoạt động khi dãy số đưuọc sắp xếp tăng dần (chính xác hơn là dãy không giảm).
hàm lower_bound(first, last, value) : trả về vị trí đầu tiên lớn hơn hoặc bằng value trong dãy.
hàm upper_bound(first, last, value) : trả về vị trí đầu tiên lớn hơn value trong dãy.

PHP:

Code này của Nguyễn Tiến Trung Kiên #include <stdio.h> #include <algorithm> using namespace std; int n, m; int a[1230997]; main(){ int i, p, q; scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); sort(a+1, a+n+1); // a[1..n] for (i=1; i<=n; i++) printf(i==n?"%d\n":"%d ", a[i]); scanf("%d", &m); // m times while (m--){ scanf("%d", &p); q = lower_bound(a+1, a+n+1, p) - a; // a[1..n], a[q]>=p if (q==n+1) printf("No numbers are bigger than %d\n", p); else printf("The 1st number >= %d is a[%d]=%d\n", p, q, a[q]); q = upper_bound(a+1, a+n+1, p) - a; // a[1..n], a[q]>p if (q==n+1) printf("No numbers are bigger than %d\n", p); else printf("The 1st number > %d is a[%d]=%d\n", p, q, a[q]); } }

Nguồn: https://sites.google.com/site/kc97ble/

lamdetien36 · 20 Tháng tám 2013

Anh cho em xin mấy bài chặt nhị phân cơ bản để em code thử với

thienvamai · 20 Tháng tám 2013

lamdetien36 said:
Anh cho em xin mấy bài chặt nhị phân cơ bản để em code thử với

bài này ko phải bài cơ bản vì phải tối ưu các kiểu mới mong đc 100 nhưng mà nếu làm đc sẽ rất thành thạo chặt nhị phân
http://vn.spoj.com/problems/GRAPE/
thường chặt nhị phân ko phải là 1 bài toán, nó chỉ là 1 phần của bài toán, chặt nhị phân thường đc ứng dụng để làm những bài QHĐ để giảm độ phức tạp.(ví dụ như cách tim dãy con tăng dài nhất trong NlogN).

lamdetien36 · 1 Tháng chín 2013

Bài NKREZ thì chặt thế nào hả anh ?
Cái đoạn này:

Mã:

function DP: integer; inline;
 var
    i, j, max: integer;
    F: array [1..10000] of integer;
 begin
      F[1] := K[1] - P[1];
      for i := 2 to N do
      begin
           max := 0;
           for j := 1 to i - 1 do if K[j] <= P[i] then
           begin
                if F[j] > max then max := F[j];
           end;
           F[i] := max + K[i] - P[i];
      end;
      DP := MaxIntValue(F[1..N]);
 end;

Có K sắp xếp tăng rồi thì chặt thế nào để tìm max hả anh

thienvamai · 3 Tháng chín 2013

thêm dòng F= max(F,F[i-1])

lamdetien36 · 3 Tháng chín 2013

thienvamai said:
thêm dòng F= max(F,F[i-1])

Ơ em hỏi cách chặt để tìm biến max ấy anh à

thienvamai · 4 Tháng chín 2013

tạo hàm max(a,b) trả về max của a và b
vứt biến max ấy đi, kết quả là F[n]
đại khái đoạn code c++ nó thế này,
mỗi a là 1 khoảng thời gian
.first là thời điểm kết thúc
.second là thời điểm bắt đầu
(viết thế này để dùng vài thứ có sẵn trong c++ ấy mà)

PHP:

for(int i=1; i<=n; i++) { F[i]=max(F[i-1],a[i].first-a[i].second); l=1; r=i-1; while(l<=r) { mid=(l+r)/2; if(a[mid].first<=a[i].second) { F[i]=max(F[mid]+a[i].first-a[i].second,F[i]); l=mid+1; } else r=mid-1; } }

Tìm kiếm

Tìm kiếm

[kĩ năng cần biết] tìm kiếm nhị phân (chặt nhị phân)

thienvamai

lamdetien36

thienvamai

lamdetien36

thienvamai

lamdetien36

thienvamai