Phương pháp tìm kiếm nhị phân mở rộng
Ví dụ: dùng tìm kiếm nhị phân để tìm phần tử có giá trị nhỏ nhất lớn hơn X trong dãy phần tử đã sắp xếp tăng dần.
Function TK_NP(x:Longint): Longint;
Var L, R, Mid: Longint;
Begin
L := 1; R := N;
while (L <= R) do
Begin
Mid := (L + R) div 2;
if (K[Mid] <= X) then L := Mid + 1
else R := Mid – 1;
End;
exit(L);
End;
Tương tự, ta có thể tìm phần tử lớn nhất nhỏ hơn giá trị X.
Bài toán áp dụng
Bài 1. Bài toán cổ
"Vừa gà vừa chó
Bó lại cho tròn
Ba mươi sáu con
Một trăm chân chẵn
Hỏi có bao nhiêu gà bao nhiêu chó?"
Bài toán cổ này chúng đã biết cách giải từ thời cấp 1. Hôm nay chúng ta cùng đi quyết bài toán tổng quát với số con gà và con chó, số chân gà và chân con chó tùy ý.
Yêu cầu: Cho biết tổng số con gà và con chó là M, tổng số chân là N. Hãy xác định số lượng con gà và con chó.
Dữ liệu vào: Đọc từ file CHICKDOG.INP chứa hai số nguyên dương M, N (2 ≤ M, N ≤ 1015; N/4 < M < N/2)
Kết quả: Ghi ra file CHICKDOG.INP chứa hai số nguyên là số con gà và con chó, nếu không có nghiệm thì in -1.
Ví dụ:
|
CHICKDOG.INP |
CHICKDOG.OUT |
|
36 100 |
22 14 |
Hướng dẫn:
Cách 1:
Thử số lượng con chó từ 1 đến N/4. Nếu số chân phù hợp thì lấy kết quả và kết thúc.
Function Timcho:Int64;
Begin
For x:=1 To N Div 4 Do
If x*4+(M-x)*2 = N) Then Exit(x;)
Exit(-1);
End;
Độ phức tạp là O(N)
Cách 2:
Sử dụng thuật toán nhị phân tìm số chó như sau:
d:=1;c:=N Div 4;
Trong khi d ≤ c thì
- g:=(d+c) Div 2;
- Nếu g*4+(M-g)*2 = N thì số chó là g và kết thúc
- Nếu g*4+(M-g)*2 > N thì số chó quá lớn thì chặt nhị phân trong đoạn d đến c=g-1
- Nếu g*4+(M-g)*2 < N thì số chó quá nhỏ thì chặt nhị phân trong đoạn d=g+1 đến c
Function Timcho:Int64;
Begin
d:=1;c:=N Div 4;
While d<=c Do
Begin
g:=(d+c) Div 2;
If g*4+(M-g)*2=N Then Exit(g);
If g*4+(M-g)*2>N Then c:=g-1
Else d:=g+1;
End;
Exit(-1);
End;
Độ phức tạp là O(LogN)