SKKN Giải một số bài toán bằng phương pháp tìm kiếm nhị phân giúp nâng cao hiệu quả bồi dưỡng học sinh giỏi

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT TRIỆU SƠN 3
SÁNG KIẾN KINH NGHIỆM
GIẢI MỘT SỐ BÀI TOÁN BẰNG PHƯƠNG PHÁP TÌM KIẾM NHỊ PHÂN GIÚP NÂNG CAO HIỆU QUẢ BỒI DƯỠNG HỌC SINH GIỎI
Người thực hiện: Lê Thị Quỳnh
Chức vụ: Giáo viên
Đơn vị công tác: Trường THPT Triệu Sơn 3
SKKN thuộc lĩnh vực (môn): Tin học
THANH HOÁ NĂM 2019
 MỤC LỤC
1. MỞ ĐẦU
1.1. Lý do chọn đề tài.
Trong các đề thi chọn học sinh giỏi (HSG) của các trường THPT trong Tỉnh, hoặc đề thi HSG cấp Tỉnh những năm gần đây, có những bài toán kích thước lớn, nếu giải bằng cách thông thường thì sẽ không tối ưu về mặt thời gian, hoặc có thể không vét hết các trường hợp xảy ra của bài toán. Tuy nhiên, nếu áp dụng phương pháp tìm kiếm nhị phân (thường gọi là chặt nhị phân) thì sẽ giải quyết tốt được tất cả các trường hợp trên.
Quá trình dạy tại các lớp mũi nhọn và ôn thi HSG cấp Tỉnh, tôi đã vận dụng phương pháp tìm kiếm nhị phân để giúp các em nhìn nhận một bài toán từ nhiều góc độ khác nhau. Qua đó có thể dễ dàng nhận ra việc áp dụng phương pháp này để giải bài toán nào đó. Vì vậy, tôi đã chọn đề tài “Giải một số bài toán bằng phương pháp tìm kiếm nhị phân giúp nâng cao hiệu quả bồi dưỡng học sinh giỏi” làm sáng kiến kinh nghiệm của mình trong năm học 2018 – 2019 để trao đổi với đồng nghiệp. Đây là một phương pháp tôi đã thực hiện rất hiệu quả tại ngôi trường THPT Triệu Sơn 3, đồng thời cũng hy vọng cách làm này sẽ được hoàn thiện, bổ sung và nhân rộng trong các trường THPT khác trong Tỉnh.
1.2. Mục đích nghiên cứu.
Với lý do chọn đề tài đã trình bày ở trên, tôi mong muốn đề tài của mình sẽ giúp đỡ phần nào các khó khăn khi nhận dạng bài toán tìm kiếm nhị phân trong quá trình ôn luyện học sinh giỏi.
- Khảo sát, đánh giá được thực trạng việc bồi dưỡng học sinh tham gia thi học sinh giỏi cấp Tỉnh của trường Trung học phổ thông Triệu Sơn 3.
- Nhìn nhận, giải quyết một số bài toán bằng phương pháp tìm kiếm nhị phân.
1.3. Đối tượng nghiên cứu.
- Thuật toán tìm kiếm nhị phân.
- Một số bài tập thi HSG các cấp.
- Sự tư duy, ý thức học tập của học sinh ôn thi học sinh giỏi.
1.4. Phương pháp nghiên cứu.
	Để thực hiện đề tài này, tôi đã sử dụng các phương pháp: 
- Phương pháp nghiên cứu xây dựng cơ sở lí thuyết: Cơ sở lý thuyết là phương pháp tìm kiếm nhị phân, một số bài toán trong các đề thi các cấp; Sự hứng thú trong giờ học môn Tin học và ý thức tự học của học sinh đối với môn học.
- Phương pháp điều tra khảo sát thực tế, thu thập thông tin: Thông qua kết quả điều tra mức độ hiểu về thuật toán tìm kiếm nhị phân của học sinh lớp 11 trường THPT Triệu Sơn 3.
- Phương pháp thống kê, xử lý số liệu: Trên cơ sở các kết quả đạt được, thống kê các số liệu, xử lí số liệu để so sánh giữa nhóm thực nghiệm và đối chứng.
2. NỘI DUNG 
2.1. Cơ sở lý luận.
Cho dãy K gồm N phần tử đã được sắp xếp theo thứ tự không giảm. Tìm xem trong dãy có giá trị nào bằng X hay không?
2.1.1. Nội dung thuật toán.
Giả sử cần tìm X trong đoạn K[L ... R] (L R), trước hết ta xét khóa nằm giữa đoạn K[Mid] với Mid = (L + R) div 2;
Nếu K[Mid] < X nghĩa là đoạn K[L ... Mid] chứa toàn khóa < X. khi đó ta tiến hành tìm kiếm X trên đoạn K[Mid+1 ... R]
Nếu K[Mid] > X nghĩa là đoạn K[L ... Mid] chứa toàn khóa > X. khi đó ta tiến hành tìm kiếm X trên đoạn K[R ... Mid - 1]
Nếu K[Mid] = X thì tìm kiếm thành công (kết thúc quá trình tìm kiếm).
Quá trình tìm kiếm sẽ thất bại nếu một bước nào đó đoạn tìm kiếm là rỗng tức là L > R
2.1.2. Nội dung chương trình bằng NNLT PASCAL.
Function	TK_NhiPhan(X: Key): integer;
var	L,R,Mid:integer;
Begin
	L := 1; R := N;
	While (L <= R) do
	Begin
	Mid := (L + R) div 2;
	if K[Mid] = X then
	Begin
	TK_NhiPhan := Mid;
	exit;
	end
	else if K[Mid] < X then L := Mid + 1
	else	R := Mid – 1;
	end;
	TK_NhiPhan := 0;
End;
2.1.3. Độ phức tạp thuật toán.
Người ta chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(logN). Phương pháp tìm kiếm nhị phân chỉ thực hiện được với dãy đã được sắp xếp, nên nếu dãy chưa sắp xếp thì cần phải tính đến thời gian cho việc sắp xếp lại dãy trước khi áp dụng tìm kiếm nhị phân.
2.2. Thực trạng của vấn đề cần giải quyết .
Nhiều học sinh có thể hiểu thuật toán tìm kiếm nhị phân nhưng việc vận dụng để giải một bài toán bằng phương pháp này thì thực sự chưa hiệu quả, chưa nhìn nhận được cách giải bài toán bằng phương pháp tìm kiếm nhị phân, nhất là các bài toán dạng tìm kiếm nhị phân “ẩn” hay nói cách khác là dạng tìm kiếm nhị phân theo kết quả.
Trong nội dung thi học sinh giỏi Tin học các cấp, có nhiều bài thường có thể giải với nhiều cách khác nhau, trong các cách đó thì không phải cách nào cũng có thể giải quyết hết các bộ dữ liệu giới hạn của bài toán, việc hướng đến giải quyết hết các test từ bé đến lớn với thời gian đảm bảo yêu cầu (thường là 1s) là vấn đề không phải học sinh nào cũng có thể làm được. Một trong những phương pháp giúp học sinh giải được khá nhiều bài ở mức độ vừa và khó là tìm kiếm nhị phân.
2.3. Các giải pháp giải quyết vấn đề.
2.3.1. Giải bài toán từ “góc nhìn” tìm kiếm nhị phân.
Mỗi bài toán nêu ra trong đề tài này là những ví dụ cho việc có thể thực hiện giải quyết bài toán bằng nhiều cách, trong đó có thể sử dụng phương pháp tìm kiếm nhị phân. Đó cũng là cách có thể thực hiện được với bộ dữ liệu từ bé đến lớn theo yêu cầu giới hạn của bài toán. Trong đề tài này, tôi chỉ nêu ra các cách giải theo ý chủ quan, vẫn có thể còn những cách làm khác mà bản thân chưa biết đến, với những cách làm khác được nêu ra, tôi chỉ nêu cách làm, còn theo cách tìm kiếm nhị phân thì tôi sẽ nêu cách làm và code bài bằng ngôn ngữ lập trình Pascal.
Bài toán 1: Taxi (Nguồn: Đề bài thi HSG cấp Tỉnh Thanh Hóa- năm học 2017-2018).
Trong dịp nghỉ hè các bạn học sinh lớp 12 dự định tổ chức dã ngoại đến biển Sầm Sơn và sẽ đi bằng taxi. Các bạn được chia thành n nhóm, nhóm thứ i gồm Si bạn (1 ≤ Si ≤ 4) và mỗi chiếc taxi chở tối đa 4 hành khách. Vậy lớp 12 cần thuê ít nhất bao nhiêu chiếc taxi để chở các nhóm đi, với điều kiện là các bạn trong nhóm phải ngồi chung taxi (một taxi có thể chở một nhóm trở lên).
Dữ liệu vào: Từ tệp văn bản TAXI.INP gồm:
- Dòng đầu chứa số nguyên n (1 ≤ n ≤ 105) (số lượng các nhóm học sinh)
- Dòng số 2 chứa dãy số nguyên S1, S2, ..., Sn (1 ≤ Si ≤ 4). Các số nguyên cách nhau bởi dấu cách với Si là số học sinh trong nhóm thứ i.
Dữ liệu ra: Ghi ra tệp văn bản TAXI.OUT là 1 số nguyên duy nhất là số lượng tối thiểu xe taxi cần thiết để chở tất cả học sinh đến nơi.
Ví dụ:	
TAXI.INP
TAXI.OUT
5
1 2 4 3 3
4
Hướng dẫn giải
Bài này có thể giải theo hai cách như sau:
Cách 1: Tư duy theo kiến thức toán học. Kết quả bài toán là tổ hợp của các trường hợp có thể xảy ra của bài toán. Theo cách làm này, học sinh khó lấy hết các test của bài vì nếu không cẩn thận sẽ không xét hết các trường hợp có thể xảy ra của bài toán. Thực tế là đã có rất nhiều học sinh bị mất điểm ở bài này theo cách làm như vậy.
	Độ phức tạp của thuật toán theo cách này là O(n)
Cách 2. Tìm kiếm nhị phân: 
	Bài này cần tìm kiếm nhị phân trên dãy dữ liệu của đề bài, nhưng trước khi tìm kiếm nhị phân, cần sắp xếp lại dữ liệu của đề bài thành dãy không giảm. Độ phức tạp của thuật toán theo cách này là O(nlogn)
 Bước 1. Sắp xếp dãy số nguyên đã cho theo thứ tự không giảm (sắp xếp mảng a); 
Bước 2. dau←1; cuoi ← n;
Bước 3. Nếu a[dau] +a[cuoi]<=4 thì 
 a[cuoi] ← a[dau]+a[cuoi] ;
 a[dau] ←0;
 dau:=dau+1;
 ngược lại thì cuoi←cuoi-1;
Bước 4. Nếu dau<cuoi thì quay lại bước 3;
Bước 5. i ← 1;
	 Bước 5.1. Nếu a[i]0 thì d← d+1 và i← i+1, ngược lại thì i← i+1;
 Bước 5.2. Nếu i<=n thì quay lại bước 5.1;
Bước 6. Đưa ra d và kết thúc.
Dưới đây là code của bài toán bằng cách tìm kiếm nhị phân:
Program TAXI;
VAR f,g: text;
 y,n,dau,cuoi,d: longint;
 a: array[1..1000000] of byte;
procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
 i:=l;
 j:=r;
 x:=a[(l+r) div 2];
 repeat
 while a[i]<x do
 inc(i);
 while x<a[j] do
 dec(j);
 if not(i>j) then
 begin
 y:=a[i];
 a[i]:=a[j];
 a[j]:=y;
 inc(i);
 j:=j-1;
 end;
 until i>j;
 if l<j then
 sort(l,j);
 if i<r then
 sort(i,r);
end;
BEGIN assign(f,'TAXI.INP');
 reset(f);
 assign(g,' TAXI.OUT');
 rewrite(g);
 readln(f,n);
 for y:= 1 to n do read(f,a[y]);
 sort(1,n);
 dau:= 1;
 cuoi:= n;
 while dau < cuoi do
 begin
 if a[dau] + a[cuoi] <= 4 then
 begin
 a[cuoi]:= a[dau] + a[cuoi];
 a[dau]:=0;
 dau:= dau+1;
 end
 else cuoi:= cuoi-1;
 end;
 for y:= 1 to n do
 if a[y] 0 then d:= d+1;
 write(g,d);
 close(f);
 close(g);
END.
Bài toán 2: Dãy con (Nguồn: Đề thi HSG cấp tỉnh Đà Nẵng năm học 2007 - 2008). 
Cho một dãy số nguyên dương a1,a2,...,aN (10 < N < 105), ai <=104 với mọi i=1..N và một số nguyên dương S (S < 108).
Yêu cầu : Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng S.
Dữ liệu vào: Đọc từ file SUB.INP gồm 2 dòng, dòng 1 chứa N và S ở dòng đầu. Dòng 2 chứa các phần tử của dãy.
Dữ liệu ra: Kết quả ghi vào file SUB.OUT, chứa độ dài của dãy con tìm được.
Ví dụ:
SUB.INP
SUB.OUT
10 15
5 1 3 5 10 7 4 9 2 8
2
* Hướng dẫn giải:
Bài toán này có thể giải theo 3 cách sau:
Cách 1: dễ dàng giải bài toán với cách là xét 2 vòng lặp lồng nhau để tìm tất cả các tổng của các đoạn con đồng thời kết hợp tìm đoạn con có tổng >= S và có số phần tử ít nhất. Độ phức tạp là O(N2). Vì vậy, cách làm này sẽ chỉ thực hiện được đến n<=104.
Cách 2: Sử dụng phương pháp tìm kiếm nhị phân để giải bài toán, độ phức tạp là theo cách này là O(NlogN):
Gọi T[i] là tổng của các số A[1] đến A[i].
Vì A[i] là các số dương nên dãy T là dãy tăng dần.
Khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau:
* Xét T[i]:
	d = 1, c = i-1,
	g = (d + c) div 2
Nếu T[i] – T[g] >= S thì kq = min(kq, i – g) và tìm kq tiếp tục ở đoạn bên phải T[g]
Nếu T[i] – T[g] < S thì tìm kq ở đoạn bên trái T[g].
Dưới đây là code của bài toán bằng cách tìm kiếm nhị phân:
Program SUB;
const fi='SUB.IN0';
 fo='SUB.OU0';
 nmax = 100000;
 oo = 100001;
Var A,T:array[0..nmax] of longint;
 N,S,kq:longint;
 F:text;
procedure doc;
var i:longint;
Begin
 assign(F,fi);
 reset(F);
 T[0] := 0;
 Readln(F,N,S);
 for i:=1 to N do
 Begin
 read(F,A[i]);
 T[i] := T[i-1] + A[i];
 end;
 close(F);
end;
function min(a,b:longint):longint;
Begin
 if a > b then min := b
 else min := a;
end;
procedure xuly;
var i,d,c,g:longint;
Begin
 kq := oo;
 for i:=1 to N do
 Begin
 d := 1; c := i-1;
 While d <= c do
 Begin
 g := (d + c) div 2;
 if T[i] - T[g] >= S then
 Begin
 kq := min(kq,i-g);
 d := g + 1;
 end
 else c := g - 1;
 end;
 end;
end;
procedure ghi;
Begin
 assign(F,fo);
 rewrite(F);
 if kq = oo then write(F,0)
 else Write(F,kq);
 close(F);
end;
BEGIN
 doc;
 xuly;
 ghi;
END.
Cách 3: Bài toán có thể giải với độ phức tạp là O(N).
Xét tổng đoạn T = A[d] + A[d+1] + A[d+2] + + A[c]
Nếu T = S
Nếu T <= S thì cập nhật lại kq, vì kết quả là đoạn ngắn nhất nên nếu loại bỏ A[d] đi để được đoạn ngắn hơn đoạn trước đó.
Bài toán 3: Lucky number
Chí Phèo thời IT rất yêu thích các số Lucky. Số Lucky là số mà chỉ chứa các chữ số Lucky (có hai chữ số Lucky là 4 và 7) trong biểu diễn thập phân. Các số Lucky sắp xếp tăng dần tạo thành dãy số Lucky. Một số số hạng đầu tiên của dãy số Lucky là: 4,7,44,47,74,77, Biết Chí có niềm yêu thích như vậy, Thị Nở liền đố Chí tìm số Lucky thứ K trong dãy. Bài toán thực sự hóc búa với Chí, bạn hãy giúp anh Chí câu hỏi này nhé!. Biết rằng:
Dữ liệu vào: Từ tệp LUCKY.INP gồm số n (n109) duy nhất.
Dữ liệu ra: Ghi vào tệp LUCKY.OUT chứa số Lucky tìm được
Ví dụ:
LUCKY.INP
LUCKY.OUT
4
47
Hướng dẫn giải
Bài này có thể giải theo những cách như sau:
Cách 1. Xét lần lượt các số tự nhiên từ 1 đến max. Với mỗi số i, kiểm tra xem nó có là số may mắn hay không? Cứ như thế cho đến khi nào tìm được số may mắn thứ n. Độ phức tạp của thuật toán theo cách này là O(n) * độ phức tạp của hàm kiểm tra số may mắn.
Cách 2. Ta nhận thấy: Có 2k số may mắn có độ dài k :
- Số thứ nhất là 	4
- Số thứ hai là	7 	Vậy tổng có 2 số có 1 chữ số, 21 = 22 - 2.
- Số thứ ba là	44
- Số thứ tư là	47
- Số thứ năm là	74
- Số thứ sáu là	77	Vậy tổng có 22 +21 chữ số = 23 - 2
	 	444	
	447
	474
Có 8 số có 3 chữ số
Vậy tổng có 23 + 22 + 21 =24 -2
	477
	744
	747
	774
777
Với mỗi k=1,2,3...thì tổng số lượng các số may mắn là 22 -2 , 23 -2, 23-2, ...Vậy, nếu gọi vị trí của số đó là n thì số thứ n sẽ luôn lớn hơn một số có dạng 2x -2, tức là: 2x -2 ≤ n≤ 2x+1 -2. Ta sẽ duyệt x chạy từ 1 đến 30 (vì 231= 1073741824), nếu n nằm giữa khoảng trên thì tìm được 2 điểm đầu cuối
Vì vậy, vị trí đầu cuối để chặt nhị phân là 2x -2 và 2x+1 -2. 
Thứ hai, ta thấy các chữ số luôn chia thành hai nửa, số 4 và số 7 nên ta tìm kiếm nhị phân đoạn này thì ta sẽ tìm ra được chữ số.
Độ phức tạp của thuật toán theo cách này là O(log2x), với 1≤ x≤30
Dưới đây là code của bài toán bằng cách tìm kiếm nhị phân:
Const Fi='luckynum.inp';
 Fo=' luckynum.out';
Var F1,F2:text;
 F:array[1..30] of longint;
 N,i,dau,cuoi,giua,dem:longint;
procedure Nhap;
 begin
 assign(F1,Fi);
 assign(F2,Fo);
 reset(F1);
 rewrite(F2);
 read(F1,N);
 end;
function Lt(X:byte):longint;
 begin
 if X=0 then Lt:=1 else Lt:=2*Lt(X-1);
 end;
BEGIN
 Nhap;
 for i:= 1 to 30 do
 begin
 F[i]:=Lt(i+1)-2;
 if F[i]>N then break;
 end;
 dau:=F[i-1];
 cuoi:=F[i];
 giua:=(dau+cuoi) div 2;
 dem:=0;
 while demi do
 begin
 if N<=giua then write(F2,'4') else write(F2,'7');
 inc(dem);
 if N<=giua then cuoi:=giua else dau:=giua;
 giua:=(dau+cuoi) div 2;
 end;
 close(F1);
 close(F2);
END.
Bài toán 4: Số ngẫu nhiên. (Nguồn: Đề thi chọn đội tuyển trường năm học 2017-2018 , Trường ĐH SP Vinh). 
Cho dãy số nguyên a1,a2,..,an.Số ai được gọi là số k-ngẫu nhiên của dãy nếu trong k số hạng liên tiếp bất kì của dãy đều có ít nhất một số hạng bằng ai và k là số nguyên nhỏ nhất thỏa mãn điều kiện này.
Ví dụ: Dãy 1,2,3,1,2,2. Số 1 là số 3-ngẫu nhiên; số 2 là số 3-ngẫu nhiên; số 3 là số 4-ngẫu nhiên.
Yêu cầu: Tìm k nhỏ nhất để trong dãy có số k – ngẫu nhiên.
Input: Cho trong tệp văn bản RANNUM.INP như sau:
Dòng đầu ghi số nguyên dương n (N<=105)
Dòng thứ 2 ghi n số nguyên a1,a2,..an.(|ai|<=103).
Output: Ghi trong tệp văn bản RANNUM.OUT gồm một số k tìm được thỏa mãn yêu cầu bài toán.
Ví dụ:
RANNUM.INP
RANNUM.OUT
6
1 2 3 1 2 2
3
* Hướng dẫn giải:
Cách 1: Bài toán được giải bằng phương pháp tìm kiếm nhị phân. Độ phức tạp là O(NlogN)
Bước 1: Khởi tạo K = N (Mọi số trong dãy đều là số N – ngẫu nhiên)
Bước 2:
	d := 1; c:= k
	While d <= c do
	Begin
	g := (d+c) div 2;
	if OK(g) then {Nếu dãy có số g – ngẫu nhiên} 
	Begin
	kq := g; {lưu lại kq}
c := g – 1; {giảm g}
	end
	else {ngược lại thì tăng g} d := g + 1; 
end;
Vấn đề đặt ra là hàm OK(k) – Kiểm tra dãy có số k – ngẫu nhiên phải xử lý thế nào?
Muốn kiểm tra A[i] có phải là số k – ngẫu nhiên hay không thì chỉ việc kiểm tra trong mọi đoạn k số liên tiếp có xuất hiện A[i] không.
Dưới đây là code của bài toán bằng cách tìm kiếm nhị phân:
program RANNUM;
const fi='RANNUM.IN0';
 fo='RANNUM.OU0';
 nmax = 100000;
 amax = 1000;
var f:text;
 A:array[1..nmax+1] of longint;
 dem:array[-amax .. amax] of longint;
 N,kq:longint;
procedure doc;
var i:longint;
Begin
 assign(f,fi); reset(f);
 readln(f,N);
 for i:=1 to N do read(f,A[i]);
 close(f);
end;
function ok(k:longint):boolean;
var i,j:longint;
Begin
 fillchar(dem,sizeof(dem),0);
 for i:=1 to k do inc(dem[A[i]]);
 for i:=K+1 to N do
 if dem[A[i]]=0 then dec(dem[A[i-k]])
 else if A[i] A[i-k] then
 Begin
 inc(dem[A[i]]);
 dec(dem[A[i-k]]);
 end;
 ok := false;
 for i:=-1000 to 1000 do
 if dem[i] > 0 then
 Begin
 ok := true;
 exit;
 end;
end;
procedure nhiphan;
var g,d,c:longint;
Begin
 d := 1;
 c := N;
 While d <= c do
 Begin
 g := (d + c) div 2;
 if ok(g) then
 Begin
 kq := g;
 c:=g-1;
 end
 else d := g + 1;
 end;
end;
procedure ghi;
Begin
 assign(f,fo); rewrite(f);
 write(f,kq);
 close(f);
end;
BEGIN
 doc;
 nhiphan;
 ghi;
END.
Cách 2: Có thể sử dụng thuật toán với độ phức tạp là O(N) để giải quyết bài toán.
Ta thấy 1 trong k số đầu tiên của dãy sẽ là số k – ngẫu nhiên. 
Vì vậy sẽ dùng thêm mảng dem[-1000 .. 1000] để đếm tần số xuất hiện các của k phần tử đầu tiên trong dãy, khi đó dem[A[i]] > 0 nghĩa là A[i] có thể là số k – ngẫu nhiên.
Duyệt 1 vòng lặp: i từ k+1 đến N:
+ if dem[A[i]] = 0 then dec(dem[A[i-k]]) 
{Nếu số A[i] không xuất hiện trong k số từ A[i – k] tới A[i – 1] thì A[i] không là số k ngẫu nhiên – thì giảm dd[A[i-k]] 1 đơn vị để loại số A[i-k] này ra khỏi dãy có k số liên tiếp}
	+ if (dem[A[i]] > 0) and (dem[A[i]] dem[A[i-k]] then 
	 Begin
inc(dem[A[i]]);
dec(dem[A[i-k]]);
	 end;
{Nếu A[i] xuất hiện trong dãy A[i – k] tới A[i – 1] thì A[i] có thể là số k – ngẫu nhiên và trong dãy A[i-k+1] đến A[i] có A[i] thì tăng dem[A[i]]}
Duyệt lại lần nữa để kiểm tra xem có dd[i] > 0 hay không? Nếu có thì dãy có số k – ngẫu nhiên.
2.3.2. Phân loại các dạng thực hiện tìm kiếm nhị phân.
	Để biết một bài toán nào đó có thể sử dụng thuật toán tìm kiếm nhị phân để giải quyết hay không thì có thể qui về hai dạng như sau:
2.3.2.1. Dạng 1: Tìm kiếm nhị phân trên dãy (mảng) có sẵn.
	Đối với dạng bài này sẽ đơn giản hơn vì dãy (mảng) các phần tử cần được sắp xếp lại (hoặc đã được sắp xếp sẵn), yêu cầu bài toán cần chỉ ra kết quả có thể xuất hiện trong dãy hay không. Với n lớn hơn 104, thì không thể duyệt 2 vòng để tìm kết quả vì sẽ quá thời gian qui định (1s). Khi đó, có thể nghĩ đến sắp xếp bằng quick-sort và tìm kiếm nhị phân. Cụ thể:
Ví dụ 1: Các bài toán đã trình bày ở phần 2.3.1
Ví dụ 2. Hẹn gặp (Nguồn: Đề thi HSG cấp Tỉnh Thanh Hóa năm học 2016-2017)
Thành phố Gloaming (Hoàng hôn) nổi tiếng với đường dẫn vào công viên thành phố. Các bức tượng tuyệt đẹp theo chủ đề thần thoại Hy lạp – La mã đặt dọc theo con đường thẳng có một sức hút không cưỡng được với mọi khách du lịch. Còn khi những tia nắng cuối cùng trong ngày miễn cưỡng rời khỏi bầu trời thì sương mù dày đặc, như một tấm voan trắng mềm mại từ từ rũ xuống. Bây giờ đứng cách quá r mét là đã không nhìn thấy mặt nhau và các bức tượng trở thành nơi lý tưởng cho các đôi nam nữ thanh niên hẹn hò. 
James Bond cần gặp gấp 2 điệp viên nội tuyến của mình để nhận các mật báo khẩn. Không muốn 2 người này nhìn thấy nhau, Bond hẹn gặp mỗi người ở một bức tượng sao cho khoảng cách giữa chúng lớn hơn r. Trên đường có n bức tượng, bức tượng thứ i ở vị trí cách đầu con đường di mét i = 1 ÷ n, 1 ≤ d1< d2 < . . .< dn ≤ 109. 
Yêu cầu: Hãy xác định James Bond có bao nhiêu cách chọn địa điểm.
Dữ liệu vào: Vào từ file văn bản HENGAP.INP:
Dòng đầu tiên chứa 2 số nguyên n và r (1 ≤ n ≤ 3×105, 1 ≤ r ≤ 109).
Dòng thứ 2 chứa n số nguyên d1, d2, . . ., dn.
Kết quả: Đưa ra file văn bản HENGAP.OUT một số nguyên là số cách chọn địa điểm tìm được.
Ví dụ:
HENGAP.INP
HENGAP.OUT
4 4
1 3 5 8
2
Rằng buộc:
Có ½ số test tương ứng với ½ số điểm có n ≤ 104
Có ½ số test tương ứng với ½ số điểm có 104 < n ≤ 3×105
Ý tưởng: (Nội dung này tham khảo trong tài liệu tập huấn giáo viên 2017 )
 - Dùng một vòng lặp For – do để duyệt i từ 1 đến n-1, trong đó với mỗi vị trí i thì ta tìm kiếm nhị phân để tìm địa điểm j xa nhất thỏa mãn r+di < dj.
Ví dụ 3. (Nguồn: Đề bài hội thi chọn GVG 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 xá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ứ hai 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ứ ba 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à số cặp tìm được.
Giới hạn: 1≤ ai ≤ 109 , 1 ≤ i ≤ n