Mở rộng phương pháp tìm kiếm nhị phân

Trong các bài toán Tin học, có những bài toán không chỉ đơn thuần tìm vị trí của khóa X trong một dãy đối tượng được sắp xếp mà có thể là tìm phần tử có khóa nhỏ nhất lớn hơn X (hoặc tìm phần tử có khóa lớn nhất nhỏ hơn X). Khi đó vẫn sử dụng tìm kiếm nhị phân nhưng cần cải tiến một chút trong hàm tìm kiếm này.

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 ≤ 10¹⁵; 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ụ:

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)