Chuyên đề:
VẬN DỤNG THUẬT TOÁN

TÌM KIẾM NHỊ PHÂN
GIẢI QUYẾT MỘT SỐ BÀI TOÁN

Trường THPT chuyên Lê Hồng Phong NĐ

1


I. ĐẶT VẤN ĐỀ
Tìm kiếm là một việc thường xảy ra trong cuộc sống. Tìm kiếm luôn là
thao tác nền móng cho rất nhiều tác vụ tính toán. Thuật toán tìm kiếm nhị phân

là một trong những thuật toán tìm kiếm quan trọng nhất của tin học. Thuật
toán này còn được gọi là thuật toán chặt nhị phân hay thuật toán chia đôi được áp
dụng rất nhiều trong giải toán, nó làm giảm được nhiều thời gian tìm kiếm,
giúp chương trình chạy nhanh hơn.

IV. NỘI DUNG
1.Phương pháp tìm kiếm:
Thuật toán tìm kiếm nhị phân liên quan đến bài toán sau:
“ Cho mảng n phần tử đã được sắp tăng dần và một phần tử x. Tìm xem x
có trong mảng hay không”
Yêu cầu: Thuật toán này chỉ có thể được dùng khi dãy số được sắp xếp
đơn điệu theo thứ tự tăng hoặc giảm dần.
Tư tưởng của thuật toán: chọn phần tử ở vị trí giữa làm chốt, chia dãy
thành 2 phần có kích thước nhỏ hơn. Sau đó so sánh phần tử cần tìm x với
chốt, nếu x lớn hơn chốt tìm ở nửa sau của dãy, nếu x nhỏ hơn chốt
tìm ở nửa trước của dãy (áp dụng với dãy tăng), quá trình trên tiếp tục

x}
End;

2.Độ phức tạp :
Để 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, ta dùng chặt nhị phân để tìm kiếm thì :
Ttốt= O(1) ( x nằm ở vị trí giữa mảng)
Txấu= O(logn)
Logarit là một hàm tăng chậm. Trong trường hợp ta còn băn khoăn về tính hiệu
quả khi tìm kiếm nhị phân, hãy xét việc tìm kiếm một tên trong một cuốn danh bạ
điện thoại có chứa một triệu tên. Tìm kiếm nhị phân cho phép ta tìm thấy bất kỳ
tên nào chỉ sau nhiều nhất 21 lượt so sánh. Nếu ta có thể quản lý một danh sách
có chứa tất cả mọi người trên thế giới được sắp xếp theo tên, ta có thể tìm thấy
bất kỳ người nào trong vòng chưa đầy 35 bước.

3.Bài tập vận dụng
A.Phần bài tập cơ bản

Trường THPT chuyên Lê Hồng Phong NĐ

3


Bài 1. ĐOÁN SỐ
Hai người chơi như sau: Người thứ nhất sẽ nghĩ ra một số nguyên dương trong
khoảng từ 1 đến N (N được cho biết trước). Người thứ hai sẽ lần lượt đưa ra các
số dự đoán. Với mỗi số dự đoán này, người thứ hai sẽ nhận được câu trả lời cho
biết số mình vừa nêu ra lớn hơn, nhỏ hơn, hay bằng với số mà người thứ nhất đã
nghĩ. Em hãy giúp người thứ hai chọn đúng số cần tìm với số lần đoán càng ít

- Sắp xếp số gà theo thứ tự tăng dần (theo chiều từ dưới lên)
- Chia đôi tổng số gà, nếu tại điểm giữa đó tổng số chân gà và chân gà và chân
chó lớn hơn 100 thì lấy nửa trên, và ngược lại lấy nửa dưới.
Thuật toán:
1. d:=0; c:=36; x:=100;
2.Trong khi d2*g+4*(36-g) thì c:=g
2.4Nếu x
Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có N cây, mỗi cây có
độ cao là a1, a2,…aN.
Người ta cần lấy M mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao H
(mét) để cưa tất cả các cây có độ cao lớn hơn H (dĩ nhiên những cây có độ cao
không lớn hơn H thì không bị cưa).
Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là 20; 15; 10 và 18 mét,
cần lấy 7 mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là 15 mét thì độ cao của các cây
còn lại sau khi bị cưa tương ứng là 15; 15; 10 và 15 mét. Tổng số mét gỗ lấy
được là 8 mét (dư 1 mét).
Trường THPT chuyên Lê Hồng Phong NĐ

6


Yêu cầu: Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên H lớn nhất) sao cho lấy
được M mét gỗ và số mét gỗ dư ra là ít nhất.
Dữ liệu:
• Dòng thứ nhất chứa 2 số nguyên dương N và M (1≤N≤10 6; 1≤M≤2x109) cách

nhau một dấu cách.
• Dòng thứ hai chứa N số nguyên dương a i là độ cao của mỗi cây trong hàng

(1≤ai≤109; i=1…N), mỗi số cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra màn hình một số nguyên cho biết giá trị cần tìm.
Ví dụ:
WOOD.INP
47

WOOD.OUT
15

t:=s-m;
if (t=0 )or (cl=t)then kt:=false
else begin
cl:=t;
if t=0 then write('h=',g) else write('ko tim dc');

B. PHẦN NÂNG CAO
Trong thực tế, ta thường gặp dạng bài toán tìm thời điểm kết thúc sớm nhất (hay
muộn nhất) của một công việc, tìm chi phí bé nhất (hay lớn nhất),… với các yêu
cầu ràng buộc trong đề bài. Khi đó ta nghĩ đến một thuật toán rất hiệu quả - thuật
toán tìm kiếm nhị phân.
Sau đây là một số bài tập trong các đề thi học sinh giỏi

Bài 6. CHỈNH DÃY SỐ
Cho một dãy N (N≤2x105) số nguyên dương không quá 109. Có thể giữ
nguyên hoặc bỏ không quá một đoạn liên tiếp các số trong dãy. Hãy thực hiện
một trong hai cách trên sao cho dãy số thu được có độ dài đoạn liên tiếp tăng dần
là lớn nhất.
Ví dụ : với dãy 1 2 3 1 4 5 sẽ chỉ có cách bỏ số 1 thứ 2 trong dãy đi để thu được
dãy mới có độ dài đoạn con liên tiếp tăng dần là 5
Với dãy 1 3 4 6 ta không cần bỏ số nào đi
Dữ liệu vào từ file DEFENSE.INP
- Dòng 1 : số nguyên T≤25 là số bộ test
- T nhóm dòng sau: mỗi nhóm gồm 2 dòng. Dòng đầu ghi số nguyên N, dòng
sau ghi N số nguyên là các số trong dãy theo thứ tự từ trái qua phải
Trường THPT chuyên Lê Hồng Phong NĐ


Xét trường hợp :
+ Nếu i và j cùng thuộc một trong hai đoạn con này, giá trị max của L[i]+R[j] có
thể tính được nhờ thủ tục find(L,m) và find(m+1,R).
+ Nếu i thuộc đoạn con thứ nhất và j thuộc đoạn con còn lại, ta áp dụng Merge
sort để sắp xếp lại các A trong đoạn từ [L,R] tăng dần sau mỗi lần gọi find(L,R).
Từ đó với mỗi i∈[L,m] ta có thể tìm kiếm nhị phân ra j∈[m+1,R] tương ứng sao
cho A[j] nhỏ nhất lớn hơn A[i] và tìm ra được giá trị lớn nhất của tổng L[i]+R[i]

Cài đặt :
Program defense ;
Trường THPT chuyên Lê Hồng Phong NĐ

9


Uses math ;
Const nfi=’defense.inp’ ;
nfo=’defense.out’ ;
maxn=100010 ;
var

a,r,l,c,f,d : array[0..maxn] of longint ;

n,res,ntest :longint ;
fi,fo :text ;
procedure enter ;
var i : longint ;
begin
read(fi,n)
for i :=1 to n do read(fi,a[i]) ;

else begin
d[i] :=c[v] ; inc(v) ; end ;
for i := x to y do c[i] :=d[i] ;
end ;
procedure solve ;
var i:longint ;
begin
//tinh l,r
L[1]:=1;
For i :=2 to n do
begin
L[i] :=1
If (a[i]>a[i-1]) then l[i] :=l[i-1]+1 ;
End ;
R[n] :=1 ;
For i :=n-1 downto 1 do
begin
R[i] :=1 ;
If (a[i]
Trường THPT chuyên Lê Hồng Phong NĐ

12


Nếu A < S thì tìm kiếm trong đoạn [ Cmin , C tg -1 ]
Nếu A=S thì căn bậc N của S chính là Ctg
- Tiếp tục tìm kiếm cho tới khi Cmin >Cmax
Cài đặt:
type
ds=array[1..1000] of 0..9;
var
x,y,kqc:ds;
a,b,s,skq,stg:string;
ctg,n,m,j,k,p,spt,l,i,cmin,cmax:longint;
f,g:text;
procedure htkq(x:ds;n:longint);
var
i:byte;
begin
for i:=1 to n do write(x[i]);
end;
procedure nhan(x,y:ds;vt:byte); {Nhan mot chu so o vi tri vt cua so y voi so x}
var kq:ds;
nho,i,t,tg:byte;
begin
for k:=1 to m-vt do kq[k]:=0;
k:=m-vt;
nho:=0;
for i:=l downto 1 do

kqc[t]:=(nho+kqc[t])mod 10;
nho:=tg;
end;
kqc[t]:=nho+kqc[t];
spt:=t;
end;
procedure xlkq;
var i,j,tg:byte;
begin
i:=1;
j:=spt;

Trường THPT chuyên Lê Hồng Phong NĐ

14


while i
skq:='';
str(ctg,a);
str(ctg,b);
{tinh ctg mu n}
for p:=2 to n do
begin
l:=length(a);
m:=length(b);
for i:=1 to l do x[i]:=ord(a[i])-48;
for i:=1 to m do y[i]:=ord(b[i])-48;
for k:=1 to l+m+1 do kqc[k]:=0;
for j:=m downto 1 do nhan(x,y,j);
xlkq;
a:='';
for i:=1 to spt do
begin
str(kqc[i],stg);
a:=a+stg;
end;
end;
skq:=a;
if ss(skq,s) then cmax:=ctg-1

Trường THPT chuyên Lê Hồng Phong NĐ

16


else cmin:=ctg+1;
end;

H[i] là số hạng nhỏ nhất trong các số hạng cuối cùng của các dãy con tăng có độ
dài i. Đuơng nhiên h[1] < h[2] a[h[res]] then
Begin
Inc(Res); H[res]:=i;
End
else
Begin
d:=1; c:=Res;
While dc do
begin
mid:=(d+c+1) div 2;
If A[i] > a[h[mid]] then d:=mid else c:=mid-1;
End;
Mid:=(d+c) div 2;
If (A[h[mid]] < a[i]) and (a[i]

yugi.Inp
43

yugi.Out
2

0123
1023
2203
3330
Input: file yugi.inp
•

Dòng đầu là 2 số N,K(2 ≤ K ≤ N ≤ 200)

•

N dòng tiếp theo mỗi dòng là N số a(i,j) (a(i,j) ≤ 32767; nếu i = j thì a(i,j) =
0)

Output: file yugi.out gồm 1 dòng duy nhất là S lớn nhất

Thuật toán :
Chặt nhị phân, với mỗi giá trị V(sức mạnh) đang xét, nhóm tất cả các quân bài
(i,j) thành 1 nhóm nếu
+ i ≠ j.
+ a[i,j]
Var i,j,dem,u,v,s,Nhom,d,c:integer;
kt:boolean;
dd:array[1..Max]Of Boolean;
q:array[1..Max] Of Integer;
Begin
Nhom:=0;dem:=0;
Fillchar(dd,sizeof(dd),True);
While (dem
Writeln(Fo,kq);
End;
BEGIN
Assign(Fi,Finp);Reset(Fi);
Assign(Fo,Fout);Rewrite(Fo);
Khoitao;
Chat;
Close(Fi);Close(Fo);
END.

Bài 10. MTWALK ( />Cho một bản đồ kích thước NxN (2
finp='mtwalk.inp';
fout='mtwalk.out';
var
fi,fo : text;
n,Hmax,Hmin,d,c,V,min,max,Vtrc : integer;
Trường THPT chuyên Lê Hồng Phong NĐ

23


a : array[0..101,0..101] of longint;
t : array[0..101,0..101] of boolean;
ok : boolean;
time : longint;
procedure init;
var i,j : integer;
begin
Hmin:=200;
assign(fi,finp);

Hmax:=-1;
reset(fi);

readln(fi,n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(fi,a[i,j]);
if a[i,j] < Hmin then Hmin:=a[i,j]; {tim o co do cao min}

{kiem tra cac o thoa man de di}
if (a[i+1,j]