SKKN Phương pháp chia để trị để giải quyết bài toán sắp xếp và tìm kiếm nâng cao trong quá trình bồi dưỡng học sinh giỏi môn lập trình Pascal bậc Trung học Cơ sở

điều kiện. Bài toán 2 thì được giải rất đơn giản. 
Thuật toán được viết dưới dạng giả mã như sau:
Procedure ThapHanoi;
Begin 
	Move(n,1,2,3);
end;
Procedure Move(n,a,b,c);
{chuyển n đĩa, từ vị trí a sang vị trí b, dùng vị trí c làm trung gian }
begin 
	if n=0 then exit;
	Move(n-1,a,c,b);
	writeln('Chuyển đĩa ',n, ' từ vị trí ',a, 'sang vi tri ',b);
	Move(n-1,c,b,a);
 	 end;
Chương trình trong Pascal:
Program ThapHaNoi;
var n:integer;
procedure move(n,a,b,c:integer);
begin
 if n=0 then exit;
 move(n-1,a,c,b);
 writeln('Chuyen dia ',n,' tu vi tri ',a,' sang vi tri ',b);
 move(n-1,c,b,a);
end;
begin
 write('Nhap N = ');readln(n);
 move(n,1,2,3);
 readln
end.
Chúng ta hãy dừng lại một chút để phân tích độ phức tạp tính toán. Gọi T(n) là số thao tác chuyển đĩa cần thiết để chuyển xong n đĩa. Theo thuật toán trên ta có:
T(n) = T(n-1) + 1 + T(n-1).
Bằng các phương pháp giải công thức truy hồi ta có được T(n) = 2n-1. Áp dụng kết quả này với giả thiết rằng mỗi cao tăng phải mất 1 giây để chuyển xong một đĩa từ cọc này sang cọc kia, ta thấy thời gian để chuyển toàn bộ 64 đĩa vàng là T(64)=216-1=18446744073709551615 giây. Như vậy ngày tận thế (nếu có) theo truyền thuyết phải 600 tỉ năm nữa mới đến.
b) Cách thức thực hiện phương pháp Chia để trị trong bài toán sắp xếp và tìm kiếm 
- Bài toán sắp xếp
Bài toán: Cho dãy A gồm N số nguyên. Sắp xếp dãy A thành dãy không giảm.
	Bài toán sắp xếp là bài toán quen thuộc và có nhiều thuật toán để giải bài toán này. Các thuật toán Sắp xếp nổi bọt (Bubble Sort) hay chèn trực tiếp (Insertion Sort) đều có độ phức tạp cỡ O(n2). Thuật toán sắp xếp nhanh (Quick Sort) hay sắp xếp trộn (Merge Sort) là hai thuật toán sắp xếp theo tư tưởng chia để trị. 0Với tư tưởng chia để trị, Quick Sort và Merge Sort cho ta độ phức tạp nhỏ hơn thường là O(nlogn). Trong đề tài này tôi chỉ tập trung nghiên cứu thuật toán QuickSort
	Chúng ta xét thuật toán sắp xếp nhanh (Quick Sort) 
Ý tưởng: Tư tưởng của thuật toán này là chia để trị, ta tìm cách chia đôi dãy ban đầu bằng cách chọn ra một phần tử là chốt (pivot). Từ dãy ban đầu, tất cả phần tử nhỏ hơn phần tử chốt thì đưa về bên trái dãy; những phần tử lớn hơn hoặc bằng chốt thì đưa về bên phải dãy. Sau bước này ta có phần tử chốt là đứng đúng vị trí. Dãy ban đầu được chia thành hai dãy con nằm hai bên chốt. Tiếp tục phân chia các dãy con theo cách tương tự cho đến khi mọi dãy con đều có độ dài bằng 1. Có thể chọn phần tử chốt nằm đầu, cuối, giữa dãy hoặc chọn ngẫu nhiên một phần tử trong dãy.
Giải thuật: Trường hợp sau chọn chốt là phần tử giữa dãy
	Sắp xếp một đoạn bất kỳ X[L] ... X[R] với điều kiện L<R
	Bước 1: pivot=(L+R) div 2; Key=X[pivot];
	Bước 2: i:=L; j:=R;
	Bước 3:
	Nếu X[i]<key thì tăng i;
	Nếu X[j]>key thì giảm j;
	Bước 4: Nếu i<j thì đổi chỗ X[i] và X[j], quay lại bước 3;
	Bước 5: Lặp lại bước 1 đến bước 3 với đoạn X[L] đến X[j] và X[i] đến X[H] cho đến khi tất cả các đoạn có độ dài bằng 1.
	Đoạn chương trình con:
procedure quicksort(l,h:longint);
var i,j:longint;key,tg:longint;
Begin
 i:=l;j:=h;key:=X[(l+h) div 2];
 repeat
 while b[i]>x do inc(i);
 while b[j]<x do dec(j);
 if i<=j then
 begin
 tg:=X[i];
 X[i]:=X[j];
 X[j]:=tg;
 inc(i);
 dec(j);
 end;
 until i>j;
 if i<h then quicksort(i,h);
 if j>l then quicksort(l,j);
end;
Đánh giá độ phức tạp
Việc chọn chốt để phân đoạn quyết định hiệu quả của thuật toán, nếu chọn chốt không tốt rất có thể việc phân đoạn bị suy biến thành trường hợp xấu khiến QuickSort hoạt động chậm.
Trường hợp tốt nhất: mỗi lần phân hoạch ta đều chọn được phần tử median (phần tử lớn hơn hay bằng nửa số phần tử và nhỏ hơn hay bằng nửa số phần tử còn lại) làm chốt. Khi đó dãy được phân đoạn thành hai phần bằng nhau, và ta cần log2(n) lần phân đoạn thì sắp xếp xong. Ta cũng dễ nhận thấy trong mỗi lần phân đoạn ta cần duyệt qua n phần tử. Vậy độ phức tạp trong trường hợp tốt nhất cỡ O(nlogn).
Trường hợp xấu nhất: mỗi lần phần đoạn ta chọn phải phần tử có giá trị cực đại hoặc cực tiểu làm mốc. Khi đó dãy bị phân đoạn thành hai phần không đều: một phần chỉ có một phần tử, phần còn lại có n-1 phần tử. Do đó, ta cần tới n lần phân đoạn mới sắp xếp xong. Vậy độ phức tạp trong trường hợp xấu nhất thuộc O(n2). Trường hợp này ít khi xẩy ra nếu việc chọn chốt là ngẫu nhiên.
Bài toán áp dụng:
Bài 1 : Đề thi chọn đội dự tuyển học sinh giỏi quốc gia năm học 2017– 2018 Hà Tĩnh (Bài 1- vòng 2)
	Các bến xe Buýt
	Khắc Hiếu vừa đậu đại học, cậu ra Hà Nội và gặp anh Khánh Hòa – một thành viên cũ của đội tuyển quốc gia môn Tin học. Hiếu muốn tìm hiểu về các bến xe Buýt ở Hà Nội còn Hòa thì biết rất rõ về các bến xe và số lượng xe của các bến xe. Hà Nội có N bến xe Buýt được đánh số từ 1 đến N, Hòa đố Hiếu: Hãy chọn trong N bến xe Buýt một số xe sao cho tổng số xe của 3 bến bất kỳ được chọn không lớn hơn tổng số xe của các bến còn lại và số lượng bến xe được chọn là nhiều nhất. Phần thưởng là một chuyyến dạo chơi bằng xe Buýt để ngắm thành phố Hà Nội. Bạn hãy giúp Hiếu.
	Dữ liệu vào: từ file văn bản BUYT.INP
Dòng đầu tiên ghi số N cho biết số bến xe Buýt (4≤ N≤104)
Dòng tiếp theo ghi N số nguyên dương A1 ... AN (Ai là số lượng xe của bến xe thứ i, Ai ≤ 102).
Dữ liệu ra: Ghi vào file văn bản BUYT.OUT
Dòng duy nhất ghi số lượng bến xe được chọn.
Các số trên một dòng ghi cách nhau bởi một dấu cách.
	Ý tưởng:
	Để xác định bến thứ i (i:1 – N) có thể chọn hay không ta sẽ tính tổng S của bến này với hai bến bất kỳ đã chọn và so sánh với Sum – S (Sum là tổng số xe của tất cả các bến). 
	Việc duyệt tất cả các bến, đánh dấu những bến đã được chọn và tính tổng của bến đang xét với hai bến bất kỳ được chọn sẽ dẫn đến thuật toán độ phức tạp cỡ O(n3).
Vì vậy, thay vì phải duyệt tất cả các bến ta thực hiện sắp xếp các bến xe theo thứ tự tăng dần của số lượng xe. Khi đó để xét bến thứ i có thể chọn hay không ta chỉ cần tính tổng S của bến này với hai bến đứng trước nó trong dãy đã sắp xếp. Nếu S Sum – S, khi đó số bến đã được chọn sẽ là nhiều nhất.
Phân tích độ phức tạp của thuật toán:
Ta nhận thấy việc tính tổng Sum và tính tổng của 3 bến liền kề có độ phức tạp nhỏ hơn hoặc bằng cỡ O(n). Như vậy độ phức tạp của thuật toán chủ yếu là ở thuật toán sắp xếp. Nếu ta sử dụng Quick Sort thì độ phức tạp của thuật toán cỡ O(nlogn).
Chương trình:
{$OBJECT FPC}
const
 nmax=100000;
var a:array[1..nmax]of longint;
 n:longint;
procedure enter;
var i:longint;f:text;
begin
 assign(f,’BUYT.inp’);Reset(f);
 readln(f,n);
 for i:=1 to n do
 read(f,a[i]);
	 Close(f);
end;
procedure quicksort(l,h:longint);
var i,j,x,tg:longint;
begin
 i:=l;
 j:=h;
 x:=a[(l+h) shr 1];
 repeat
 while a[i]<x do inc(i);
 while a[j]>x do dec(j);
 if i<=j then
 begin
 tg:=a[i];
 a[i]:=a[j];
 a[j]:=tg;
 inc(i); dec(j);
 end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure main;
var i:longint;
 sum:int64;
	 f:text;
begin
 assign(f,’BUYT.out’);rewrite(f);
 sum:=0;
 for i:=1 to n do
 sum:=sum+a[i];
 i:=n;
 while i>3 do
 if (a[i]+a[i-1]+a[i-2])<=(sum shr 1) then break
 else dec(i);
 write(f,'so xe chon duoc nhieu nhat la: ',i);
	 Close(f);
end;
BEGIN
 enter;
 quicksort(1,n);
 main;
 readln
END.
Bài 2. Đua ngựa
Ở thời Xuân Thu, vua Tề và Điền Kỵ thường hay tổ chức đua ngựa từng cặp với nhau. Mỗi một con ngựa có một hệ số khác nhau. Trong cuộc đua, con ngựa nào có hệ số cao hơn thì sẽ thắng, nếu có hệ số ngang nhau thì sẽ về đích cùng một lúc mỗi một con ngựa chỉ được thi đấu một lượt. Ai có tổng số trận thắng nhiều hơn thì sẽ thắng chung cuộc. Số trận <= 1000 trận. Bạn hãy giúp Điền Kỵ sắp xếp các lượt đấu để đạt số trận thắng cao nhất có thể.
Dữ liệu vào từ file DUANGUA.INP bao gồm:
- Dòng đầu là số lượng ngựa: n 
- Dòng thứ hai có n số, số thứ i là hệ số của con ngựa thứ i của Điền Kỵ.
- Dòng thứ ba có n số, số thứ i là hệ số của con ngựa thứ i của vua Tề.
Kết quả ghi vào file DUANGUA.OUT gồm 1 số duy nhất ghi số trận thắng cao nhất mà Điền Kỵ có thể dành được.
DUANGUA.INP
	5
	3 7 12 5 8
	13 5 9 14 6
	DUANGUA.OUT
	3
 Ví dụ:	
DUANGUA.INP
	3
	4 6 2
	9 3 5	
	DUANGUA.OUT
	2
	Ý tưởng: 
	Với mục tiêu dành nhiều trận thắng nhất có thể nên Điền Kỵ phải cố gắng đưa ra con ngựa thi đấu sao cho nó sẽ đấu với đối thủ mạnh nhất có thể của vua Tề mà vẩn dành được phần thắng
	Để thực hiện được điều này ta sắp xếp hệ số của các con ngựa của cả Điền Kỵ và Vua Tề theo thứ tự giảm dần. Khi đó, con ngựa mạnh nhất sẽ được đưa ra thi đấu trước và nó sẽ thi đấu với con ngựa đầu tiên tìm được (Từ đầu dãy ngựa của Vua Tề trở đi) mà nó có thể thắng. Lần lượt như thế cho đến khi các chú ngựa của Điện Kỵ thi đẫu hết.
	Với Input:
	3
	4 6 2
	9 3 5
	Ta sắp xếp hai dãy số thành
	6 4 2 và 9 5 3
	Khi đó con ngựa có hệ số 6 của Điền Kỵ sẽ đấu với con ngựa hệ số 5 của Vua Tề và được một trận thắng. Con ngựa có hệ số 4 của Điền Kỵ sẽ đấu với con ngựa hệ số 3 của Vua Tề và được trận thắng thứ hai. Cặp ngựa còn lại Điền Kỵ bị thua và số trận thắng nhiều nhất có thể là 2.
	Chương trình:
{$OBJECT FPC}
const
 nmax=10000;
 Type mang=array[1..nmax] of integer;
var a,b:mang;
 n:integer;
procedure enter;
var i:longint;f:text;
begin
 assign(f,'DUANGUA.inp');reset(f);
 readln(f,n);
 for i:=1 to n do
 readln(f,a[i]);
 readln(f);
 for i:=1 to n do
 readln(f,b[i]);
 close(f);
end;
procedure quicksort(var x:mang;l,h:integer);
var i,j,key,tg:integer;
begin
 i:=l;
 j:=h;
 key:=x[(l+h) shr 1];
 repeat
 while x[i]<key do inc(i);
 while x[j]>key do dec(j);
 if i<=j then
 begin
 tg:=x[i];
 x[i]:=x[j];
 x[j]:=tg;
 inc(i);
 dec(j);
 end;
 until i>j;
 if j>l then quicksort(x,l,j);
 if i<h then quicksort(x,i,h);
end;
procedure main;
var i,j,d:integer;f:text;
Begin
 i:=1;j:=1;d:=0;b[n+1]:=maxint;
 repeat
 while (a[i]<=a[j]) do inc(j);
 if j<=n then inc(d);
 inc(i);inc(j);
 until (i>n) or (j>n);
 assign(f,'DUANGUA.out');rewrite(f);
 write(f,d);
 close(f);
end;
Begin
 enter;
 quicksort(a,1,n);
 quicksort(b,1,n);
 main;
end.
	Bài 3.
Thằng Bờm đi mua bi ở siêu thị. Trong siêu thị có M loại bi khác nhau, loại màu i có ai hộp, mỗi hộp chứa bi viên bi. Giá mỗi hộp là như nhau và Bờm đủ tiền mua N hộp. Cậu muốn mua được nhiều bi nhất có thể.
Hãy xác định số bi nhiều nhất Bờm có thể mua.
Ví dụ:
	N=7, M=3
	ai	bi
	5 10
	2 5
	3 6
Output: 62 (Mua 5 hộp màu 1; 2 hộp màu 3)
Ý tưởng
Sắp xếp dãy B chứa các viên bi của các hộp có trong siêu thị theo thứ tự giảm dần. Đồng thời sắp xếp dãy A theo dãy B.
Nếu số hộp nhỏ thua a1 ta có số bi mua được là N*b1; nếu không ta lần lượt chọn số hộp a1, tiếp đến a2, ... cho đến khi số hộp bằng N.
Dùng biến Sum để tính tổng số bi nhiều nhất mà Bờm có thể mua được.
Chương trình
Program MuaBi;
var m,n,i:integer;
 a,b:array[1..1000] of integer;
 d,sum,s,res:integer;
Procedure nhap;
var i:integer;
Begin
 Write('nhap n,m');readln(n,m);
 for i:=1 to m do
 readln(a[i],b[i]);
end;
procedure QuickSort(l,H:integer);
var i,j,x,tg1,tg2:integer;
begin
 i:=l;j:=h;x:=b[(l+h) div 2];
 repeat
 while b[i]>x do inc(i);
 while b[j]<x do dec(j);
 if i<=j then
 begin
 tg1:=b[i];
 b[i]:=b[j];
 b[j]:=tg1;
 tg2:=a[i];
 a[i]:=a[j];
 a[j]:=tg2;
 inc(i);dec(j);
 end;
 until i>j;
end;
Begin
 nhap;
 QuickSort(1,m);
 s:=1;sum:=0;res:=0;i:=1;d:=1;
 While s<=N do
 begin
 sum:=res+d*b[i];
 d:=d+1;inc(s);
 if d>a[i] then
 begin
 i:=i+1;
 res:=sum;
 d:=1;
 end;
 end;
 write('tong so bi la ',sum);
 readln
end.
	Đánh giá thuật toán:
	Việc tìm Sum chỉ cần duyệt các giá trị của ai số lần duyệt tối đa là N vì thế độ phức tạp của thuật toán chỉ phụ thuộc vào việc sắp xếp dãy B. Với QuickSort độ phức tạp của thuật toán có cỡ O(nlogn).
	Bài 4. Tổ chức tham quan
	Trong đợt tổ chức tham quan danh lam thắng cảnh quanh thành phố Buôn Ma Thuột, công ty du lịch Bảo An tổ chức cho N đoàn (Đánh số từ 1 đến N) mỗi đoàn đi tham quan một địa điểm khác nhau. Đoàn thứ i thăm địa điểm cách khách sạn Sài Gòn Ban Mê di km (i=1,..,n). Công ty Bảo An có m xe đánh số từ 1 đến m (m≥n) để phục vụ việc đưa các đoàn đi tham quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km
	Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi tham quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
	Dữ liệu vào: File văn bản P2.inp
Dòng đầu tiên ghi hai số nguyên dương m, n
Dòng thứ hai ghi các số nguyên dương d1,..,dn.
Dòng thứ ba ghi các số nguyên dương v1,..,vm.
Kết quả: Ghi ra file văn bản P2.out
Dòng đầu tiên ghi tổng số xăng cần dùng cho việc đưa các đoàn đi tham quan (Không tính lượt về)
Dòng thứ i trong N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1,..,n)
	Ý tưởng:
Sắp xếp dãy số mức tiêu thụ xăng V của các xe theo thứ tự tăng dần.
Sắp xếp dãy số quảng đường đi của các đoàn theo thứ tự tăng dần.
Mức tiêu thụ xăng thấp nhất là: Min = ∑dn-i+1*vi với i=1,..,n. Chỉ số xe phục vụ các đoàn là giá trị từ 1 đến n trong dãy ID.
(Để ngắn gọn chương trình ta cũng có thể thực hiện sắp xếp dãy D theo thứ tự tăng dần (như bài Đua Ngựa) và tính Min = ∑dn-i+1*vi với i=1,..,n. Để tường minh và dễ hiểu tôi viết cả hai chiều sắp xếp)
Chương trình
{$OBJECT FPC}
const
 nmax=1000;
 Type mang=array[1..nmax] of integer;
var d,v,id:mang;
 n,m:integer;
 min:longint;
procedure enter;
var i:longint;f:text;
begin
 assign(f,'P2.inp');reset(f);
 fillchar(id,sizeof(id),0);
 readln(f,m,n);
 for i:=1 to n do
 readln(f,d[i]);
 readln(f);
 for i:=1 to m do
 begin
 readln(f,v[i]);
 id[i]:=i;
 end;
 close(f);
end;
procedure quicksort(l,h:integer);
var i,j,key,tg,tg1:integer;
begin
 i:=l;
 j:=h;
 key:=v[(l+h) div 2];
 repeat
 while v[i]<key do inc(i);
 while v[j]>key do dec(j);
 if i<=j then
 begin
 tg:=v[i];
 v[i]:=v[j];
 v[j]:=tg;
 tg1:=id[i];
 id[i]:=id[j];
 id[j]:=tg1;
 inc(i);
 dec(j);
 end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure quicksort2(l,h:integer);
var i,j,key,tg:integer;
begin
 i:=l;
 j:=h;
 key:=d[(l+h) div 2];
 repeat
 while d[i]>key do inc(i);
 while d[j]<key do dec(j);
 if i<=j then
 begin
 tg:=d[i];
 d[i]:=d[j];
 d[j]:=tg;
 inc(i);
 dec(j);
 end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure main;
var i:integer;f:text;
Begin
 QuickSort(1,m);
 QuickSort2(1,n);
 min:=0;
 for i:=1 to n do min:=min+v[i]*d[i];
 assign(f,'P2.out');rewrite(f);
 writeln(f,min);
 for i:=1 to n do Write(f,id[i],' ');
 close(f);
end;
Begin
 enter;
 main;
end.
	Đánh giá thuật toán:
	Thuật toán có độ phức tạp cỡ O(nlogn).
Bài 5. Trò chơi (Đề thi dự phòng HSG tỉnh 2018– Tin THCS)
	Nhân dịp lễ giáng sinh, công viên trung tâm thành phố Buôn Ma Thuột tổ chức trò chơi "con số may mắn". Mỗi em nhỏ đến tham dự sẽ được phát một số nguyên dương. Công viên có một thiết bị quay số, mỗi lần quay sẽ tạo ngẫu nhiên một số nguyên dương có giá trị tuyệt đối không vượt quá 104. Người dẫn chương trình sẽ thực hiện N lần quay số. Số nào xuất hiện nhiều nhất trong N lần quay được gọi là con số may mắn và em nhỏ nào có con số may mắn thì sẽ được phần thưởng.
Yêu cầu: Cho N con số xuất hiện trong N lần quay. Bạn hãy giúp người dẫn chương trình xác định số lần xuất hiện của con số may mắn. 
Dữ liệu vào từ file văn bản TC.inp: 
Dòng đầu là số N (1 £ N £ 104).
Dòng tiếp theo có N số là các số xuất hiện trong N lần quay.
Kết quả ghi ra file văn bản TC.out: 
Gồm một dòng duy nhất ghi số lần xuất hiện của con số may mắn. 
Ví dụ:
TC.inp
TC.out
TC.inp
TC.out
5
4 3 4 4 15
3
7
12 5 10 5 8 10 9
2
Ý tưởng:
Ngoài phương pháp sử dụng kỹ thuật đánh dấu bài toán trên còn có thể sử dụng thuật toán sắp xếp như sau:
Sắp xếp dãy theo chiều tăng dần
Max:=0;
Đếm các phần tử cạnh nhau và bằng nhau, tìm số lượng phần tử nhiều nhất:
i:=1;
repeat
	d:=1;
	while a[i]=a[i+1] do 
	begin inc(d); inc(i); end;
	if d > max then Max:=d;
	inc(i);
until i > n;
Đưa ra max.
Chương trình:
{$OBJECT FPC}
const
 nmax=1000;
 Type mang=array[1..nmax] of integer;
var a:mang;
 n,i:integer;
procedure enter;
var i:longint;f:text;
begin
 assign(f,'TC.inp');reset(f);
 readln(f,n);
 for i:=1 to n do
 readln(f,a[i]);
 close(f);
end;
procedure quicksort(l,h:integer);
var i,j,key,tg:integer;
begin
 i:=l;
 j:=h;
 key:=a[(l+h) div 2];
 repeat
 while a[i]<key do inc(i);
 while a[j]>key do dec(j);
 if i<=j then
 begin
 tg:=a[i];
 a[i]:=a[j];
 a[j]:=tg;
 inc(i);
 dec(j);
 end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure main;
var i,d:integer;f:text;
Begin
 quicksort(1,n);
 for i:=1 to n do
 if a[i]a[i+1] then inc(d);
 assign(f,'TC.out');rewrite(f);
 write(f,d);
 close(f);
end;
Begin
 enter;
 main;
end.
 Bài toán tìm kiến
Thuật toán tìm kiếm nhị phân
Bài toán: Cho dãy A gồm N số nguyên được sắp xếp theo thứ tự không giảm và một số nguyên K. Cho biết có hay không phần tử trong dãy có giá trị bằng K? 
Ý tưởng
	Sử dụng tính chất của dãy tăng ta thu hẹp phạm vi tìm kiếm sau mỗi lần so sánh khóa K với số hạng được chọn. Để làm điều đó ta chọn số hạng AGiữa ở “giữa dãy để so sánh với K, trong đó Giữa = [(n+1)/2].
	Khi đó xẩy ra một trong 3 trường hợp sau:
Nếu AGiữa = K thì Giữa là chỉ số cần tìm. Việc tìm kiếm kết thúc.
Nếu AGiữa > K thì do dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ thực hiện trên dãy từ A1 đến AGiữa-1 phạm vi tìm kiếm chỉ khoảng một nửa phạm vi tìm kiếm trước đó.
Nếu AGiữa < K thì thực hiện tìm kiếm trên dãy từ AGiữa+1 đến AN.
Quá trình tìm kiếm sẽ kết thúc khi đã tìm thấy khóa K trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
Thuật toán:
Bước 1: Nhập N và các số hạng A1 ...AN và khóa K;
Bước 2: First=1; Last=N;
Bước 3: Mid=[(First+Last)/2];
Bước 4: Nếu AMid=K thì thông báo chỉ số Mid rồi kết thúc;
Bước 5: Nếu AMid>K thì Last=Mid-1, rồi chuyển đến bước 7;
Bước 6: First=Mid+1;
Bước 7: Nếu First>Last thì thông báo dãy A không có số hạng nào bằng K rồi kết thúc; 
Bước 8: Quay lại bước 3.
Thuật toán tìm kiếm nhị phân có tư tưởng gần giống với thuật toán sắp xếp nhanh. Nó thực hiện việc tìm vị trí trung tâm, thông qua phép so sánh giữa giá trị cần tìm với giá trị tại vị trí trung tâm để quyết định vùng dữ liệu (trước hay sau vị trí trung tâm) mà giá trị đó thuộc về.
Việc tìm kiếm sẽ cứ thế tiếp tục trong 1/2 tập hợp dữ liệu vừa xác định với cùng cách thức tìm kiếm, cho tới khi giá trị tại vị trí trung tâm là giá trị cần tìm hoặc phạm vi tìm kiếm bằng rỗng thì dừng. Vì sau mỗi bước tìm kiếm miền dữ liệu lại giảm đi phân nữa, số lượng các bước tìm kiếm cũng tăng dần tới tối đa là log2(N). Vì vậy độ phức tạp của thuật toán này được xem là O(logN). 
Chúng ta sẽ xem cách cài đặt thuật toán thông qua ví dụ sau:
Bài toán áp dụng: 
Bài 1. Cho một dãy gồm N số nguyên dương, xác định xem có tồn tại hay không dãy con liên tiếp có tổng bằng K hay không?
Với bài toán này ta có thể thực hiện bằng cách duyệt tất cả các dãy con có thể có từ dãy N phần tử và thực hiện tính tổng của dãy con đó rồi so sánh với K. Giải thuật có thể thực hiện như sau:
For i:=1 to N do
	Begin
	S:=0;
	For j:=i to N do S:=S+A[j];
	If s=k then begin write(‘tim thay’);break; end;
End;
Thuật toán trên cho ta độ phức tạp cỡ O(n2). Ta có thể cải tiến thuật toán bằng nhận cách sau:
Tạo dãy S trong đó Si=A1+...+Ai;
Nhận thấy do dãy A gồm các số nguyên dương nên dãy S là tăng dần.
Để xác định đoạn [Ai,Aj] có tổng các phần tử bằng K hay không ta thực hiện tìm kiếm nhị phân trên đoạn từ vị trí i đến vị trí j trong dãy S mà Sj-Si=K. 
Giải thuật như sau:
Bước 1. Tạo dãy S từ dãy A: 
	S[0]:=0;
	Với mỗi i nhận giá trị từ 1 đến n làm S[i]:=S[i-1]+A[i];
Bước 2. Res=-1; {Res dùng để đánh dấu vị trí cuối của dãy con cần tìm}
Bước 3. Với mỗi i nhận giá trị từ 1 đến N làm:
 3.1 Cho first:=i; last:=n;
 3.2 chừng