SKKN Thuật toán tìm kiếm nhị phân trong bồi dưỡng học sinh giỏi môn Tin học

MỤC LỤC
Trang
I. MỞ ĐẦU
1
1. Lý do chọn đề tài
1
2. Mục đích nghiên cứu.
1
3. Phạm vi đề tài
2
4. Phương pháp nghiên cứu
2
II. NỘI DUNG
1. Cơ sở lý luận
3
3
a.Thuật toán tìm kiếm nhị phân cơ bản
3
b. Cài đặt
5
c. Đánh giá độ phức tạp thời gian của thuật toán
5
2. Các biến thể của thuật toán tìm kiếm nhị phân (Thuật toán tìm một phần tử có giá trị gần bằng X)
6
a. Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)
b. Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)
c. Dãy con tăng –Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)
e. Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x
d. Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x
6
6
7
7
8
3. Bài tập áp dụng
a. Bài toán 1: Bước nhảy xa nhất (Đề thi lớp 11 trại hè Hùng vương năm 2014)
b. Bài toán 2: (Đề thi giáo viên giỏi cấp tỉnh Thanh Hóa năm học 2013-2014)
c. Bài toán 3: CAKES
d. Bài toán 4: BÍ HIỂM
III. KẾT LUẬN VÀ ĐỀ XUẤT
8
8
9
10
12
16
Tài liệu tham khảo
I. MỞ ĐẦU
1. Lý do chọn đề tài
Thuật toán và tư duy thuật toán là một nội dung quan trọng hình thành văn hóa tin học phổ thông xuyên suốt toàn cấp trung học phổ thông. Đây là vấn đề khó và đã được đưa vào từ lớp 10 để học sinh có điều kiện tiếp thu nhanh hơn kiến thức ở lớp 11. Tuy nhiên trong bồi dưỡng học sinh giỏi thuật toán là vấn đề trọng tâm và cốt lõi. Học sinh cần phải hiểu rất kỹ về thuật toán và học các thuật toán điển hình.
Trong chương trình sách giáo khoa Tin học lớp 10 đã lựa chọn các bài toán điển hình ở dạng đơn giản nhất là sắp xếp và tìm kiếm. Các thuật toán giải các bài toán đã được trình bày khá kỹ lưỡng từ đơn giản đến phức tạp. Trong đó thuật toán tìm kiếm nhị phân được đánh giá là khó đối với học sinh trung học phổ thông nói chung. Vì vậy thuật toán này đã được giảm tải trong chương trình học đại trà. Tuy nhiên trong bồi dưỡng học sinh giỏi môn tin các cấp thì thuật toán tìm kiếm nhị phân lại đặc biệt quan trọng. 
Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó. Đây là thuật toán rất quan trọng trong Tin học, đượ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.
Với những lí do trên tôi chọn đề tài ‘‘Thuật toán tìm kiếm nhị phân trong bồi dưỡng học sinh giỏi môn Tin học“
2. Mục đích nghiên cứu
Trong phạm vi đề tài của mình tôi muốn nghiên cứu các biến thể của thuật toán tìm kiếm nhị phân và một số bài tập khi áp dụng thuật toán tìm kiếm nhị phân và các biến thể của nó. Thông qua đó cung cấp thêm một phương pháp tư duy, tiếp cận để giải các bài toán trong bồi dưỡng HSG cấp tỉnh, giúp học sinh hình thành kỹ năng giải bài toán tin học và rèn luyện tư duy thuật toán, từ đó rèn luyện tư duy lập trình. Cũng qua đề tài, tôi muốn cùng đồng nghiệp trao đổi, trau dồi chuyên môn nhằm góp phần nâng cao trình độ chuyên môn nghiệp vụ và khả năng mở rộng kiến thức. Với bản thân nghiên cứu đề tài sáng kiến kinh nghiệm là cơ hội tốt để nghiên cứu khoa học làm quen với phương pháp làm khoa học tuy chỉ trong phạm vi hẹp nhưng tôi hy vọng cùng với nổ lực của bản thân và sự giúp đỡ của đồng nghiệp sẽ có những đề tài khoa học tốt, lý thú và hiệu quả.
3. Phạm vi đề tài
Đề tài này được áp dụng đối với học sinh khá và giỏi với nhiệm vụ chủ yếu là ôn thi học sinh giỏi và bồi dưỡng kiến thức cho học sinh yêu thích môn tin.
4. Phương pháp nghiên cứu
Để hoàn thành đề tài này, tôi đã tiến hành áp dụng một số phương pháp nghiên cứu sau: Phương pháp đặt vấn đề - giải quyết vấn đề, Phương pháp phân tích tổng hợp, Phương pháp so sánh đối chiếu, Phương pháp thực nghiệm.
II. NỘI DUNG
1. Cơ sở lý luận
a.Thuật toán tìm kiếm nhị phân cơ bản
Bài toán: Cho dãy A gồm N phần tử nguyên từ A1, A2,...An được sắp xếp thành dãy không giảm và một số nguyên 
Yêu cầu: Tìm kiếm nhị phân là một giải thuật tìm kiếm nhanh. Giải thuật này làm việc dựa trên nguyên tắc chia để trị (Divide and Conquer). Để giải thuật này có thể làm việc một cách chính xác thì tập dữ liệu nên ở trong dạng đã được sắp xếp.
Tư tưởng thuật toán: Tìm kiếm nhị phân tìm kiếm một phần tử cụ thể bằng cách so sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Nếu phần tử cần tìm là lớn hơn giá trị phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa; nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ tiếp tục như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này.
Giả sử chúng ta cần tìm vị trí của giá trị 31 trong một mảng bao gồm các giá trị như hình dưới đây bởi sử dụng Binary Search:
Đầu tiên, chúng ta chia mảng thành hai nửa theo phép toán sau:
chỉ-mục-giữa=ban-đầu + (cuối+ban-đầu)/2
Với ví dụ trên là 0 + (9 – 0)/ 2 = 4 (giá trị là 4.5). Do đó 4 là chỉ mục giữa của mảng.
Bây giờ chúng ta so sánh giá trị phần tử giữa với phần tử cần tìm. Giá trị phần tử giữa là 27 và phần tử cần tìm là 31, do đó là không kết nối. Bởi vì giá trị cần tìm là lớn hơn nên phần tử cần tìm sẽ nằm ở mảng con bên phải phần tử giữa.
Chúng ta thay đổi giá trị ban-đầu thành chỉ-mục-giữa + 1 và lại tiếp tục tìm kiếm giá trị chỉ-mục-giữa.
ban-đầu = chỉ-mục-giữa + 1
chỉ-mục-giữa=ban-đầu + (cuối+ban-đầu)/2
Bây giờ chỉ mục giữa của chúng ta là 7. Chúng ta so sánh giá trị tại chỉ mục này với giá trị cần tìm.
Giá trị tại chỉ mục 7 là không kết nối, và ngoài ra giá trị cần tìm là nhỏ hơn giá trị tại chỉ mục 7 do đó chúng ta cần tìm trong mảng con bên trái của chỉ mục giữa này.
Tiếp tục tìm chỉ-mục-giữa lần nữa. Lần này nó có giá trị là 5.
So sánh giá trị tại chỉ mục 5 với giá trị cần tìm và thấy rằng nó kết nối.
Do đó chúng ta kết luận rằng giá trị cần tìm 31 được lưu giữ tại vị trí chỉ mục 5.
Tìm kiếm nhị phân chia đôi lượng phần tử cần tìm và do đó giảm số lượng phép so sánh cần thực hiện nên giải thuật tìm kiếm này được thực hiện khá nhanh.
b. Cài đặt
Function Tknpcb(X:longint):longint;
Var d, c, g: Longint;
Begin
d:=1; 
c:=N;
While d<=c Do
Begin
g:=(d + c) Div 2;
if A[g]=X then exit(g);
if A[g]<X then d:=g+1
else c:=g-1
end;
Exit(0);
End.
 Thuật toán trên sẽ trả ra chỉ số của một phần tử có giá trị bằng X, Nếu không có giá trị nào bằng X thì hàm sẽ nhận giá trị bằng 0
c. Đánh giá độ phức tạp thời gian của thuật toán
Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào O(n), trong đó
n là độ lớn đầu vào, tùy thuộc từng bài toán mà n có thể nhận những giá trị khác nhau.
Để tìm kiếm một phần tử trong mảng. Với thuật toán tìm kiếm tuần tự, 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ì :
Trường hợp tốt nhất: Tương ứng với sự tìm được x trong lần so sánh đầu tiên, tức là x= a[giữa] (x nằm ở vị trí giữa mảng)
=> Ta có : Ttốt (n) = O(1)
Trường hợp xấu nhất: Độ phức tạp là O(log n)
Thật vậy, nếu gọi T(n) là độ phức tạp của thuật toán, thì sau khi kiểm tra điều kiện ( x = a[giữa]) và sai thì gọi đệ qui thuật toán này với dữ liệu giảm nửa, nên thỏa mãn công thức truy hồi :
T(n) = 1 + T(n/2) với n>=2 và T(1) = 0
Với phương pháp truy hồi, có thể viết
T(n)=1+1+T(n/22)
 =1+1+1+T(n/23)
Như vậy T(n) có dạng T(n)=k+T(n/2k) 
Cuối cùng ta có thể chứng minh được T(n)=[log2n]+1 hay T(n)=O(log2n)
Rõ ràng so với thuật toán tìm kiếm tuần tự, chi phí tìm kiếm nhị phân ít hơn rất nhiều. Đây cũng là phương pháp tìm kiếm dựa trên giá trị so sánh được đánh giá là tốt nhất. Tuy nhiên nếu dãy khóa luôn biến động (được bổ sung thêm hoặc loại bớt đi) thì lúc đó chi phí cho sắp xếp lại nổi lên rất rõ và chính điều này bộc lộ nhược điểm của phương pháp tìm kiếm nhị phân.
2. Các biến thể của thuật toán tìm kiếm nhị phân (Thuật toán tìm một phần tử có giá trị gần bằng X)
Trên thực tế không lúc nào người ta cũng yêu cầu tìm kiếm một phần tử bằng X mà có thể yêu cầu tìm phần tử gần bằng X nhất. Vì vậy với các bài khác nhau với các yêu cầu tìm kiếm khác nhau có thể dễ dàng sửa đổi cho phù hợp nếu sử dụng cách tìm kiếm nhị phân mình vừa trình bày.
a. Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)
function tim2(r,x : longint) : longint;
 var d,c,g : longint;
 begin
    d:=0;c:=r;
    g:=(d+c) div 2;
    while (gd) and (gc) do
      begin
        if b[g]>=x then c:=g else d:=g;
        g:=(d+c) div 2;
      end;
    for g:=c downto  d do
    if b[g]<x then exit(g);
   end;
b. Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)
sort(a);
function tim2(r,x : longint) : longint;
var d,c,g : longint;
d:=1, c=r;
g := (d + c) / 2;
while (d= g) and (g = c) do
begin
    	if a[g]>=x then c := g;
    	else d:= g;
end;
    	g := (d + c) / 2;
for g := d to c do
if a[g]>=x then exit(g);
end;
c. Dãy con tăng –Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)
sort(a);
function tim2(r,x : longint) : longint;
var d,c,g : longint;
d:=1, c:=r;
g:= (d + c) / 2;
while (d=g) and (g=c) do
begin
   	 if a[g]>x then c := g;
    	else d:= g;
    	g:= (d + c) / 2;
end;
for g := c to d do
if a[g]<=x then exit(g);
end;
d. Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x
function tim1(r,x : longint) : longint;
 var d,c,g : longint;
 begin
    d:=0;c:=r;
    g:=(d+c) div 2;
    while (gd) and (gc) do
     begin
        if b[g]>x then d:=g else c:=g;
        g:=(d+c) div 2;
      end;
    for g:=c downto d do
      if b[g]>x then exit(g);
 end;
e. Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x
function tim1(r,x : longint) : longint;
  var d,c,g : longint;
  begin
    d:=0;c:=r;
    g:=(d+c) div 2;
    while (gd) and (gc) do
      begin
        if b[g]>x then d:=g else c:=g;
        g:=(d+c) div 2;
      end;
    for g:=d to c do
      if b[g]>x then exit(g);
  end;
3. Bài tập áp dụng
a. Bài toán 1: Bước nhảy xa nhất (Đề thi lớp 11 trại hè Hùng vương năm 2014)
Cho dãy A gồm N phần tử nguyên không âm A1, A2,...An . Một bước nhảy từ phần tử Ai đến phần tử Aj được gọi là bước nhảy xa nhất của dãy nếu thỏa mãn các điều kiện sau:
+ 1 ≤i < j ≤ N.
+Aj–Ai≥P
+ j –i lớn nhất (Khi đó j –i được gọi là độ dài bước nhảy xa nhất của dãy
Yêu cầu: Tìm độ dài bước nhảy xa nhất của dãy A
Dữ liệu vào: Từ tệp JUMP.INP cps cấu trúc sau:
Dòng 1: Gồm hai số nguyên N và P (1≤ N≤105 ; 0≤ P≤109).
Dòng 2: Gồm N số nguyên A1, A2,...An (0≤ Ai≤109 với 1≤ i≤N)
Kết quả ghi vào têp JUMP.OUT gồm một số nguyên dương duy nhất là độ dài của bước nhảy xa nhất của dãy (Nếu không có bước nhảy nào thỏa mãn thì ghi kết quả bằng 0)
JUMP.IN
JUMP.OUT
6 3
4 3 7 2 6 4
3
Giải thuật:
- Gọi T[i] là phần tử nhỏ nhất từ A1 đến Ai. Vậy T là dãy giảm dần
- Duyệt tất cả các chỉ số từ j đến N. Với mỗi số j ta tìm kiếm nhị phân trên đoạn chỉ số [1,j-1] của dãy T phần tử lớn nhất thỏa mãn ≤A[j] –p
b. Bài toán 2: (Đề thi giáo viên giỏi cấp tỉnh Thanh Hóa năm học 2013-2014)
Xét dãy số nguyên dương khác nhau từng đôi một a1, a2,....an. Với số nguyên x cho trước. Hãy các định số cặp (ai, aj) thỏa mãn các điều kiện:
+ ai+aj=x
+ 1≤i, j≤n
Dữ liệu vào: File văn bản BAI3.INP:
+ Dòng đầu tiên chứa số nguyên dương n.
+ Dòng thứ 2 chứa n số nguyên a1, a2,....an, mỗi số cách nhau ít nhất một dấu cách trống.
+ Dòng thứ 3 chứa số nguyên x.
Kết quả ra: File văn bản BAI3.OUT chứa một số nguyên là cặp số tìm được.
Giới hạn: 1≤ ai≤109 ; 1≤ i≤ n ≤105;1≤x≤2.109
Ví dụ: 
BAI3.IN
BAI3.OUT
9
5 12 7 10 9 1 2 3 11
13
3
Thuật toán
- Đầu tiên ta sắp lại dãy số theo thứ tự tăng dần.
- Bước tiếp theo ta lần lượt xét các số hạng từ a1 đến an-1, khi xét đến số hạng ai ta tìm chỉ số j1 nhỏ nhất thỏa mãn j1 > i và ai + aj1 = x trên đoạn từ i +1 đến n của dãy đã sắp bằng tìm kiếm nhị phân, ta tìm tiếp chỉ số j2 nhỏ nhất thỏa mãn j2 > i và ai + aj2 = x trên đoạn từ j1 đến n của dãy đã sắp bằng tìm kiếm nhị phân (đây là các bài toán cơ bản), tất nhiên nếu j1 không tồn tại thì không tìm j2 nữa.
Nếu không tồn tại j1 và j2 thì xét sang số hạng tiếp theo, ngược lại ta cộng thêm vào tổng s một lượng là j2- j1 +1.
c. Bài toán 3: CAKES
Nghệ nhân nấu ăn Tư Mập có thể sử dụng hệ thống gồm n bếp điện để thực hiện nấu món ăn khiến ông được vinh danh, đó là món “gatô hải sản”. Thời gian để thực hiện nấu một suất ăn như vậy trên các bếp điện tương ứng là t1, t2, , tn giây.
Yêu cầu: Cho biết s là số lượng thực khách cần phục vụ, hãy xác định thời gian tối thiểu cần thiết để Nghệ nhân Tư Mập có thể nấu xong s suất ăn trên hệ thống bếp điện của khách sạn. Để nấu mỗi suất ăn chỉ được sử dụng một bếp.
Dữ liệu: Vào từ file văn bản CAKES.INP:
- Dòng đầu tiên chứa số lượng suất ăn s (0 < s < 1015) và số lượng bếp điện n (0 < n < 20).
- Dòng thứ hai chứa n số nguyên dương t1, t2, , tn, mỗi số nhỏ hơn 500.
Kết quả: Ghi ra file văn bản CAKES.OUT duy nhất một số nguyên là thời gian tối thiểu tìm được tính bằng giây.
Ví dụ:
CAKES.INP CAKES.OUT
3 2
50 70 100
Thuật toán
Ta chặt nhị phân thời gian tối thiểu phải tìm theo đề bài (trong chương trình ta dùng biến kq để biểu diễn giá trị này). Ban đầu phạm vi tìm kiếm thuộc đoạn [L =1, R = s * 500] (thời gian tối thiểu để nấu xong s suất ăn không thể nhỏ hơn 1 và không thể lớn hơn s * 500 vì thời gian nấu một suất ăn <= 500). Với mỗi giá trị gi := (L +R) div 2 (với gi là giữa) ta kiểm tra xem với thời gian là gi thì có thể nấu xong s suất ăn hay không (OK(gi) = true), nếu được thì ta gán cho biến kq bằng gi và thay đổi phạm vi tìm kiếm như sau: R := gi -1; (tìm kiếm ở nửa trái), nếu không được thì ta thay đổi phạm vi tìm kiếm bằng cách L:= gi +1 (tìm kiếm ở nửa bên phải). Khi quá trình lặp tìm kiếm nhị phân kết thúc, giá trị trong biến kq là giá trị cần tìm.
Việc xây dựng hàm OK(t:int64) (OK(t) = true nếu với thời gian là t có thể nấu xong s suất ăn) có thuật toán như sau: trong thời gian t số suất ăn mà bếp 1 nấu được là t div t1 , bếp 2 nấu được t div t2 ,.., bếp n nấu được là t div tn . Cộng tất cả số suất ăn của n bếp nấu được là SL, nếu SL >= s thì OK(t) :=true, ngược lại thì OK(T) := false.
Chương trình
const
 fi='cakes.inp';
 fo='cakes.out';
var
 f:text;
 s,n,kq:longint;
 a:array[1..21] of longint;
procedure doc;
var
 i:longint;
begin
 assign(f,fi);
 reset(f);
 readln(f,s,n);
 for i:=1 to n do read(f,a[i]);
 close(F);
end;
function ok(d:longint):boolean;
var
 sl,i:longint;
begin
 sl:=0;
 for i:=1 to n do
 sl:=sl+(d div a[i]);
 if sl>=s then exit(true) else exit(false);
end;
procedure xuli;
var
 l,r,gi:longint;
begin
 l:=1;r:=s*500;
 while l<=r do
 begin
 gi:=(l+R) shr 1;
 if ok(gi) then
 begin
 kq:=gi;
 r:=gi-1;
 end
 else
 l:=gi+1;
 end;
end;
procedure ghi;
begin
 assign(f,fo);
 rewrite(f);
 write(F,kq);
 close(F);
end;
begin
 doc; 
xuli; 
ghi;
end.
d. Bài toán 4: BÍ HIỂM
 Bà của Ellenora thường ra cho cháu gái mình những bài toán đố mà Elly coi là bí hiểm. Buổi tối vừa rồi bà đố Elly bài toán sau:
“Ở cửa hàng cạnh nhà ta có k mặt hàng với giá khác nhau từ 1 đến k. Bà có n đồng tiền mệnh giá a1, a2, . . ., an. Bà định sang bên đấy mua một mặt hàng nào đó, trả đúng giá của nó mà không phải nhận lại tiền thừa. Nhưng bà đã già quá rồi. Bà không muốn mang tất cả tiền của mình đi, có thể lẫn hoặc rơi mất, vì vậy bà chỉ mang theoít nhất có thể được một số đồng đầu tiên. Vậy bà phải mang theo bao nhiêu đồng tiền để mua được mặt hàng bất kỳ?”
Chỉ mất vài giây Elly đã đưa ra được câu trả lời và nghĩ thầm trong bụng: “Ôi, bà ơi, lại những bài toán giải thuật quá chuẩn!”.
Bạn có thể đua tài với Elly bằng cách viết chương trình giải bài toán này được không?
Dữ liệu: Vào từ file văn bản RIDDLE.INP:
Dòng đầu tiên chứa số nguyên T – số lượng tests trong file,
Mỗi test cho trên 2 dòng:
- Dòng thứ nhất chứa 2 số nguyên n và k (1 ≤ n ≤ 105, 1 ≤ k ≤ 106),
- Dòng thứ 2 chứa n số nguyên a1, a2, . . ., an , (0 < ai ≤ 105, "i = 1 ÷ n).
Kết quả: Đưa ra file văn bản RIDDLE.OUT, kết quả mối test đưa ra trên một dòng dưới dạng số nguyên. Nếu không có cách mang thì đưa ra số -1.
Ví dụ:
RIDDLE.INP
RIDDLE.OUT
3
7 10
1 2 3 4 5 6 7
3 3
2 4 1
3 6
3 1 4
3
4
-1
Thuật toán
Sau đây tác giả chỉ xin trình bày thuật toán xử lý một bộ test (nếu file input nhiều bộ test thì chỉ thêm một vòng lặp vào phần xử lý).
Bài toán này ta sẽ chặt nhị phân theo số đồng tiền đầu tiên phải mang theo, ban đầu phạm vi tìm kiếm là đoạn [1, N]. Với mỗi giá trị gi:=(L +R) div 2, Ta kiểm tra xem OK(gi) có bằng true hay không (nghĩa là với gi đồng tiền đầu tiên luôn có thể chọn ra một số đồng có tổng là i với i bất kỳ thuộc đoạn từ 1 đến k (nghĩa là có thể mua bất kỳ món hàng nào mà không phải nhận tiền thừa). Nếu OK = true thì kq := gi và R := gi -1, ngược lại L:= gi +1;
Phần khó của thuật toán này chính là xây dựng hàm OK
Hàm OK(u: longint) : boolean được xây dựng với thuật như sau: 
Ta sắp xếp u đồng tiền đầu tiên theo thứ tự tăng của mệnh giá, Lần lượt xét các đồng tiền từ số 1 đến số u có mệnh giá tương ứng là a1 ,.., au, , khi xét đến đồng tiền thứ i ta làm như sau: Ta gọi s là giá trị lớn nhất thỏa mãn với i- 1 đồng tiền đầu tiên (i-1 đồng này đã sắp xếp tăng) có thể mua được bất kỳ mặt hàng nào có giá từ 0 đến s mà không phải nhận tiền lẻ (với i = 1 thì s = 0). Nếu ai > s +1 thì OK := false ( nghĩa là với u đồng tiền đầu tiên không thỏa đề bài vì không thể mua được mặt hàng có gia là s +1 vì i-1 đồng tiền đầu không mua được mặt hàng này, các đồng tiền từ đồng thứ i đến đồng thứ u có mệnh giá lớn hơn s + 1 nên cũng không giúp gì hơn) và không xét các đồng tiền thứ i +1 đến đồng thứ u nữa. Nếu ai = k thì OK := true ngược lại OK := false; 
Chương trình
Const
 fi='riddle.inp';
 fo='riddle.out';
 nmax=100010;
var
 f,f1:text;
 a,a1:array[1..nmax] of longint;
 n,k:longint;
 s:int64;
function ok(u:longint):boolean;
var
 i:longint;
begin
 s:=0;
 for i:=1 to u do
 if a1[i]<=s+1 then s:=s+a1[i]
 else
 exit(false);
 if s>=k then exit(true);
 exit(false);
end;
procedure quicksort(l,r:longint);
var
 i,j,c,gi:longint;
begin
 i:=l;j:=r;
 gi:=a1[l+random(r-l+1)];
 repeat
 while a1[i]<gi do inc(i);
 while a1[j]>gi do dec(j);
 if i<=j then
 begin
 c:=a1[i];a1[i]:=a1[j];a1[j]:=c;
 inc(i);dec(j);
 end;
 until i>j;
 if l<j then quicksort(l,j);
 if i<r then quicksort(i,r);
end;
procedure xuli;
var
 l,r,kq,gi,i:longint;
begin
 l:=1;r:=n;
 kq:=-1;
 while l<=r do
 begin
 gi:=(l+r) shr 1;
 for i:=1 to gi do a1[i]:=a[i];
 quicksort(1,gi);
 if ok(gi) then
 begin
 kq:=gi;
 r:=gi-1;
 end
 else
 l:=gi+1;
 end;
 writeln(f1,kq);
end;
procedure process;
var
 ntest,itest,i:longint;
begin
 readln(f,ntest);
 for itest:=1 to ntest do
 begin
 readln(f,n,k);
 for i:=1 to n do read(f,a[i]);
 xuli;
 end;
end;
begin
 assign(f,fi);reset(f);
 assign(f1,fo);rewrite(f1);
 process;
 close(f1);close(f);
end.
III. KẾT LUẬN VÀ ĐỀ XUẤT
Thuật toán tìm kiếm nhị phân là một trong những thuật toán được sử dụng để bồi dưỡng học sinh giỏi, thuật toán nằm trong chương trình giảm tải đối với học sinh phổ thông nói chung, tuy nhiên rất cần thiết cho bồi dưỡng học sinh giỏi cấp tỉnh, bởi lẽ thuật toán này giúp học sinh có năng khiếu tin học được phát triển về khả năng lập trình và giải quyết các bài toán trong tin học. 
Đề tài đã nghiên cứu các biến thể của thuật toán tìm kiếm nhị phân và một số bài tập ứng dụng. Tôi hy vọng nhận được sự giúp đỡ, góp ý của đồng nghiệp để bài viết được hoàn thiện hơn, góp phần nhỏ cho công tác bồi dưỡng học sinh giỏi. 
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ Thanh Hóa, ngày 10 tháng 5 năm 2018
	 Tôi xin cam đoan SKKN này không sao
	 sao chép nội dung của người khác.