[Chuyên đề] Tìm kiếm nhị phân (Chặt nhị phân)

BINARY SEARCH : (tìm kiếm/chặt nhị phân)
Là 1 pp tìm kiếm kết quả dựa vào tính thứ tự của tập hợp thay cho cách tìm kiếm thông thường
Pp tìm kiếm thỏa mãn :
Trên 1 dãy tuyến tính tăng/ giảm theo cùng 1 tiêu chí nào đó
Thỏa mãng dc tính chất của đề bài, lập luận thỏa mãn (nếu tôi đi lùi thì chỉ thu dc kết quả xấu hơn, còn đi tiếp thì hi vọng thỏa mãn)
Độ phức tạp : O(log2n), nhanh nhiều so với O(n)

Ví dụ 1: cho 1 tập n phần tử (a[i] < a[I + 1]) , vị trí của phần tử có giá trị là val dc nhập từ INPUT

Code:


function bs : integer;
var
  l,r : integer;
  mid : integer;
begin
  l :=1;r := n;
  while l <= r do
    begin
      mid := (l + r) div 2;
      if a[mid] = val then exit(mid);
      if a[mid] < val then l := mid  + 1
      else
        r := mid - 1;
    end;
  exit(-1);
end;


Ví dụ 2 : cho 1 tập n phần tử (a[i] < a[I + 1]) , vị trí của phần tử có giá trị là val dc nhập từ INPUT sao cho độ lệch của val – a[i] là nhỏ nhất
C1 : ta val - cho dãy, bs như trên
C2 : ta chặt nhị phân như sau :

Code:


function bs : integer;
var
  l,r : integer;
  mid : integer;
begin
  l := 1; r := n;
  while abs(l - r) <> 1 do
  begin
    mid := (l + r) div 2;
    if val = a[mid] then exit(mid);
    if val < a[mid] then r := mid
    else
      l := mid;
  end;
  if (abs(val - a[l]) < abs(val - a[r])) then exit(l)
    else exit(r);
end;


NOTE :
note 1 : cách làm ở trên áp dụng cho 1 dãy mảng (1 dòng), ta cũng có thể áp dụng cách này cho pp tìm kiếm trên 2 dòng
note 2 : có nhiều cách chặt nhị phân , không nhất thiết là phải như trên, ta xét các trường hợp sau :
cách 1 :
while I <= j do -> I := mid +1; j := mid – 1
cách này ta làm khi muốn tìm chính xác phần tử hay giá trị thỏa mãn nhu cầu duyệt, không chắc rằng làm cách này có thể giải quyết dc bài toán tìm độ lêch và cung hok nên dùng cách này để giải quyết những bài toán tối ưu
1 biến thể của cách 1 cũng khá hay là: (biến thể này có thể giải quyết cho bài toán tối ưu)
While I < j do
Begin
Mid := (I + j + 1) div 2;
I := mid;
J := mid – 1;
End;
cách 2 :
while abs(I - j) <> 1 do -> I := mid; j := mid
cách này là 1 pp rất hay để tìm vị trí phần tử tối ưu, dạng bài toán tìm độ lệch, chú ý rằng giá trị tối ưu sẽ nằm trong 2 giá trị l,r nên ta phải kt thêm 1 lần nữa
ngoài ra, cách 2 còn có các biến thể :
while I <> j do -> I := mid + 1;j := mid
thực chất 2 cách làm đều tương tự nhau, nếu quen dùng cách nào chỉ nên dùng cách đó, ở đay liệt kê ra chỉ là 1 số cách hay gặp trong code của 1 số ng :D
note 3 : chặt nhị phân trên chính trục số thì làm tương tự như trên cũng ổn
note 4 : chặt nhi phân trên trụ tọa độ, ta có pp làm như sau :
while dau – cuoi < eps do
begin
mid = (dau + cuoi) / 2;
dau := mid;
cuoi := mid;
end;
note 5 : hàm lower_bound, up_bound tưa tựa bên C++ bằng cách tìm độ lêch giữa giá trị cho và pt mảng nhỏ nhất, rồi theo yêu cau lower hay up ta tìm trong khoảng (1,val) hay là (val,n) (tìm tiếp bằng độ lệch)

PP xe ủi (chế)

Code:


Trong 1 số bài toán, thay vì sort lại kết quả của bài toán, ta có thể sử dụng thêm 1 mảng b[] dùng lưu giá trị sao cho : B[i] = way(b[i],b[I + 1]) (way() ở đây có thể là min, max, etc …)
sau khi init  B[] xong, ta có thể binary search theo yêu cầu của đề bài
note : muốn sử dụng thì phải cm tính đúng đắn của nó rồi mới sử dụng
example : problem điển hình của lớp toán này là bài toán tìm a[j] xa a[i] nhất sao cho a[i] > a[j]


Problem about binary search :
LIS vn.spoj.pl/problems/LIS/
RIDDLE vn.spoj.pl/problems/RIDDLE/
YUGI vn.spoj.pl/problems/YUGI/ (1 bài tương tự là bài 8.5 sách “Tài liệu chuyên tin 3” - NXBGD)
MTWALK vn.spoj.pl/problems/MTWALK/
NKSPILJA vn.spoj.pl/problems/NKSPILJA/ (chia nhị phân trong hình học)
96B- lucky number [You must be registered and logged in to see this link.]
42A - Guilty — to the kitchen! [You must be registered and logged in to see this link.]
159B - Matchmaker [You must be registered and logged in to see this link.]
68B – Energy exchange [You must be registered and logged in to see this link.] (chú ý chuyển mọi pin đều chuyển x năng lượng)
91B – Queue [You must be registered and logged in to see this link.] (dùng pp xe ủi :D)
16C – Monitor [You must be registered and logged in to see this link.]
140C – New year snowmen [You must be registered and logged in to see this link.]

bạn cho mình hỏi bài RIDDLE (spoj) và Lucky Number (codeforce) chia nhị phân như thế nào vậy? mình cũng đang tìm hiểu phần này đây nhưng ví dụ thì ít quá mà trình độ thì có hạn .