Sáng kiến kinh nghiệm Vận dụng thuật toán tìm kiếm nhị phân vào giải một số bài toán bằng ngôn ngữ lập trình C++ và Python

 PHẦN I. ĐẶT VẤN ĐỀ 
 1. Lý do chọn đề tài 
 Môn Tin học giữ vai trò chủ đạo trong việc chuẩn bị cho học sinh khả năng tìm 
kiếm, tiếp nhận và mở rộng tri thức cũng như sáng tạo trong thời đại thông tin, hỗ 
trợ đắc lực trong quá trình học tập và tự học của học sinh. 
 Điều đó khẳng định vai trò và vị trí quan trọng của Tin học đối với toàn xã hội. 
 Do đó mỗi người, mỗi học sinh cần hiểu và trang bị kiến thức cơ bản về Tin 
học để có thể theo kịp với thời đại, với sự phát triển của xã hội. Vì vậy khi học tin 
thì cần trang bị kiến thức, kỹ năng lập trình để giải quyết bài toán dễ dàng hơn. 
Trong chương trình giáo dục phổ thông 2018 thì ngôn ngữ lập trình Python đã đưa 
vào dạy học từ lớp 10 năm học 2022-2023, Ngoài ngôn ngữ lập trình Python thì 
C++ là ngôn ngữ lập trình hiện nay rất phổ biến trong chương trình dạy học cũng 
như tính ứng dụng ngôn ngữ này rất nhiều, nhất là trong các kỳ thi tin học trẻ, thi 
vào chuyên tin, học sinh giỏi tỉnh 
 Khi giải các bài toán Tin học người lập trình luôn mong muốn viết chương 
trình với thuật toán tối ưu, thời gian thực hiện nhanh, bộ nhớ hạn chếTuy nhiên, 
bài toán Tin học thường đa dạng, phong phú nên để có thể tìm được thuật toán tối 
ưu phù hợp dữ liệu bài toán là việc không hề dễ dàng. Trong lập trình tin học đã có 
rất nhiều phương pháp giải các bài toán nhưng để đảm bảo thời gian, không gian là 
không dễ. Vì vậy lựa chọn thuật toán để tối ưu là rất quan trọng. 
 Qua quá trình giảng dạy, học tập, tìm tòi và đặc biệt là tham gia bồi dưỡng học 
sinh giỏi nhiều năm qua, trong đề thi 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 “Vận dụng thuật toán tìm kiếm 
nhị phân vào giải một số bài toán bằng ngôn ngữ lập trình C++ và Python ". 
 Đề tài ngoài tập trung nghiên cứu về thuật toán tìm kiếm nhị phân, đưa ra 
những ứng dụng của thuật toán khi giải các bài toán trên máy tính. Nhằm giúp học 
sinh vận dụng thuật toán này linh hoạt, giúp cải tiến về thời gian và không gian khi 
gặp các dạng bài toán này, cũng như các em hiểu kỹ hơn khi học chuyên đề tin 11 
(Khoa học máy tính) trong năm học tới. Ngoài ra tôi cung cấp bộ test cho các bài 
tập giúp học sinh tự luyện code một cách hiệu quả nhất. Để cải thiện thời gian 
thuật toán thì cần kết hợp thuật toán tìm kiếm nhị phân với một số phương pháp 
 1 
 PHẦN II: NỘI DUNG 
I. Cơ sở lý luận và thực tiễn 
1. Cơ sở lý luận 
 Giới thiệu thuật toán tìm kiếm nhị phân, các hàm tìm kiếm nhị phân có sẵn trong 
C++, Python cũng như nhìn nhận đánh giá được độ phức tạp thuật toán. 
1.1. Thuật toán tìm kiếm nhị phân là gì? 
Thuật toán tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm trong 
một danh sách đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Thuật toán này 
hoạt động bằng cách so sánh giá trị tại vị trí giữa danh sách với giá trị cần tìm 
kiếm. Nếu giá trị tại vị trí giữa bằng giá trị cần tìm kiếm, thuật toán sẽ trả về vị trí 
đó. Nếu giá trị tại vị trí giữa lớn hơn giá trị cần tìm kiếm, thuật toán sẽ tiếp tục tìm 
kiếm trong nửa đầu tiên của danh sách. Nếu giá trị tại vị trí giữa nhỏ hơn giá trị cần 
tìm kiếm, thuật toán sẽ tìm kiếm trong nửa sau của danh sách. Quá trình này được 
lặp lại cho đến khi tìm thấy giá trị cần tìm kiếm hoặc danh sách chỉ còn một phần 
tử. 
1.2. Khái niệm hàm lower_bound, upper_bound, bisect_left, bisect_right có 
sẵn trong C++ và Python. 
1.2.1. Giới thiệu về hàm lower_bound, bisect_left trong C++ và Python 
- Hàm lower_bound(a+1, a+n+1,x) -a với a[0]=-∞; a[n+1]=+∞: Đưa ra vị trí đầu 
tiên trong mảng a có giá trị >= x (từ vị trí 1 đến n), nếu không có x trong mảng a 
thì nó sẽ đưa kết quả là (n+1). 
- Hàm bisect_left(a, x): Cho ra vị trí đầu tiên trong mảng a có giá trị >= x; nếu 
không có x trong mảng a thì đưa ra kết quả là (n). Tương tự ta có thể đưa ra vị trí 
đầu tiên với giá trị a[k] >=x từ đoạn i đến j dùng hàn bisect_left(a, x,lo=i,hi=j); nếu 
không tìm thấy trả về vị trí hi. 
Áp dụng: Cho dãy số nguyên a1, a2, a3,..., an đã được sắp xếp không giảm và một 
số nguyên x. Tìm vị trí k nhỏ nhất sao cho a[k] >= x. 
Trong C++: kq = lower_bound(a+1, a+n+1, x) - a. 
Trong Python: kq= bisect.bisect_left(a,x); 
1.2.2. Giới thiệu về hàm upper_bound, bisect_right trong C++ và Python 
- Hàm upper_bound(a+1,a+n+1,x)- a với a[0]=-∞; a[n+1]=+∞: Đưa ra vị trí đầu 
tiên trong mảng a có giá trị > x (từ vị trí l đến n), nếu không có x trong mảng a thì 
nó sẽ đưa kết quả là (n+1). 
- Hàm bisect_right(a, x): Cho ra vị trí đầu tiên trong mảng a có giá trị >x; nếu 
không có x trong mảng a thì đưa ra kết quả là (n). Tương tự ta có thể đưa ra vị trí 
đầu tiên với giá trị a[k] >x từ đoạn i đến j dùng hàm bisect_right(a,x,lo=i,hi=j); nếu 
không tìm thấy trả về vị trí hi. 
 3 
 THPT học Python giúp các em say mê, hứng thú, yêu thích đối với ngôn ngữ lập 
trình ngày càng nhiều hơn. 
- Ngày nay máy tính ngày càng có tốc độ xử lý cao đáp ứng được yêu cầu xử lý các 
bài toán có dữ liệu lớn trong thời gian thực hiện ngắn. 
- Các cuộc thi lập trình này ngày càng tổ chức nhiều hơn, việc học, xem tài lệu, 
luyện làm code cũng dễ dàng hơn, có thể xem các tài liệu trên web cũng như các 
kênh như youtube. 
2.1.2 Khó khăn 
- Ngôn ngữ lập trình Python còn khá mới mẽ, những kiến thức trong chương trình 
Tin học phổ thông còn hạn chế, hoặc chưa đủ đáp ứng cho việc giải một số bài 
toán trong các kỳ thi học sinh giỏi Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian 
thực hiện ngắn. 
- Thuật toán tìm kiếm nhị phân thường được dạy ngay sau giai đoạn học sinh học 
xong phần kĩ thuật lập trình cơ bản. Thời điểm này, học sinh đã có thể sử dụng 
ngôn ngữ lập trình cùng với các công cụ có sẵn trong thư viện để thể hiện thuật 
toán. Tuy nhiên, khả năng tự mình nhìn nhận, đánh giá và thiết kế được một thuật 
toán cho bài toán mới còn hạn chế. 
- Khi gặp các bài toán phải sử dụng kiểu dữ liệu lớn nhiều em lúng lúng. Việc giải 
các bài toán với kiểu dữ liệu lớn thực sự cần thiết cho các em khi làm các bài toán 
lập trình trong chương trình Tin học phổ thông nói riêng và việc giải quyết các bài 
toán thực tế nói chung. 
- Thực tế cho thấy, các đề thi HSG của tỉnh và các tỉnh đều có các bài tập tìm kiếm 
với số lớn. Nếu học sinh không hiểu rõ và nhận biết tốt thì thường khi giải các bài 
tập này hay gặp nhiều sai sót hoặc không xử lý hết test theo yêu cầu. 
2.2. Thực trạng trước khi áp dụng đề tài 
- 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 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. 
 5 
 1.2 . Nội dung chương trình bằng C++ và Python 
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 
Với đầu vào là một mảng đã sắp xếp arr và giá trị cần tìm x, hàm binary_search() 
sẽ trả về chỉ số đầu tiên của x trong arr nếu x có tồn tại trong mảng và -1 nếu 
không. 
Độ phức tạp thuật toán: O(logn) 
2. Phân loại thuật toán tìm kiếm nhị phân 
2.1. Giải bài toán bằng tìm kiếm nhị phân 
Ví dụ 1: Đoạn con ngắn nhất (Đề thi thử cụm Nam Đàn 2022) 
 5 6
Cho một dãy số nguyên dương a1, a2, ..., aN (10 <N < 2*10 ), ai<=10 với mọi i=1.. 
N và một số nguyên dương k (S < 109). 
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 k. 
Dữ liệu vào: Đọc từ file SUB.INPgồ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 17 2 
 5 1 3 5 10 7 4 9 2 8 
Bài này ta có thể dụng nhiều cách giải quyết bài toán như 2 vòng for, 2 con trỏ tuy 
nhiên tôi chỉ đưa ra theo phương pháp tìm kiếm nhị phân. 
 7 
 Hướng giải quyết 2: Sử dụng tìm kiếm nhị phân theo kết quả 
Ý tưởng thuật toán: 
 - Gọi g là đoạn ngắn nhất cần tìm đoạn [1, n]. Nếu kiểm tra g thỏa mãn thì cập 
 nhật và đi tìm g nhỏ hơn thỏa mãn tức là tìm g bên trái trên đoạn [d, g-1] 
 ngược lại tìm g trên đoạn [g+1, c]. 
 - Hàm check nhiệm vụ kiểm tra đoạn độ dài g trượt trên mảng s sao cho s[i]-
 s[i-g] >= x hay không. Nếu lớn hơn trả về true ngược lại trả về false 
Độ phức tạp thuật toán: O(nlogn) 
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 
Hướng giải quyết 3: Sử dụng hàm lower_bound, upper_bound, bisect_left, 
bisect_right 
Ý tưởng thuật toán: Ta sử dụng mảng s để lưu trữ tổng từ phần tử đầu tiên đến 
phần tử thứ i của mảng a. Sau đó, duyệt từng phần tử i của mảng a, tính tổng k = x 
+ s[i], sử dụng hàm lower_bound, bisect_left để tìm vị trí đầu tiên trong mảng s mà 
có giá trị lớn hơn hoặc bằng k. 
 9 
 capso.inp capso.out 
 10 7 7 
 5 2 5 3 4 3 1 6 4 0 
Hướng giải quyết 1: Sử dụng tìm kiếm nhị phân trên dãy số 
Ý tưởng thuật toán: Sắp xếp dãy tăng dần, sử dụng tìm kiếm nhị phân như sau. 
- Để giải quyết bài toán này, ta sắp xếp tăng dần mảng. Với mỗi phần tử S[i] trong 
mảng, ta sẽ tìm kiếm phần tử S[j] thỏa mãn S[i] + S[j] = B. Sử dụng thuật toán tìm 
kiếm nhị phân, ta có thể tìm kiếm S[j] trên đoạn từ 1 đến i. Tuy nhiên, khi tìm 
kiếm phần tử S[j] để tạo thành cặp với S[i], ta cần đảm bảo rằng j < i để tránh đếm 
một cặp phần tử trùng lặp. 
- Sau khi đã tìm được tất cả các cặp phần tử trong mảng, ta cần đếm số cặp có tổng 
bằng x và xuất kết quả. Nếu có k phần tử trong mảng có giá trị bằng x/2, ta sẽ đếm 
số cặp (k*(k-1))/2 để tránh đếm một cặp trùng lặp. 
Độ phức tạp thuật toán: O(nlogn) 
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 
 11 
 vì sẽ quá thời gian qui định (1s). Khi đó, có thể nghĩ đến sắp xếp và tìm kiếm nhị 
phân. 
Bài 1: Chia kẹo1 (Đề HSG lớp 9 Bảng B Nghệ An 2021) 
 Có gói kẹo được đánh số hiệu từ 1 đến . Gói kẹo thứ 푖 (푖 = 1, 2, 3, , ) 
 có 푖 chiếc kẹo. Cần phân chia gói kẹo thành 2 phần: Phần 1 gồm các gói kẹo 
 1, 2, , 푖. Tổng số chiếc kẹo của phần 1 là = 1 + 2 + ⋯ + 푖. Phần 2 gồm các 
 gói kẹo 푖 + 1, 푖 + 2, , . Tổng số chiếc kẹo của phần 2 là = 푖+1 + 푖+2 +⋯ + 
 ; Với 1 ≤ 푖< . 
 Yêu cầu: Tìm cách phân chia gói kẹo sao cho chênh lệch giữa số kẹo của hai 
 phần là nhỏ nhất, tức là | - | đạt giá trị nhỏ nhất. Ta đặt giá trị = | - |. 
 Dữ liệu cho trong tệp văn bản ChiaKeo.Inp gồm: 
 • Dòng thứ nhất ghi số nguyên dương là số gói kẹo (1 < ≤ 105). 
 3
 • Dòng thứ hai ghi số nguyên dương 1, 2,  , (1 ≤ 푖≤ 10 ) là số chiếc 
 kẹo của gói kẹo. Các số ghi trên một dòng cách nhau bởi dấu cách. 
 Kết quả ghi ra tệp văn bản ChiaKeo.Out là giá trị nhỏ nhất của . 
 Ví dụ: 
 ChiaKeo.Inp ChiaKeo.Out Giải thích 
 5 1 Phần 1: Chọn các gói kẹo 1, 2, 3; = A1 + 
 1 2 3 4 3 A2 + A3 = 1 + 
 2 + 3 = 6. 
 Phần 2: Chọn các gói kẹo 4, 5; = A4 + 
 A5 = 4 + 3 = 7. ⇒ Chênh lệch số kẹo giữa 
 hai phần là 7 – 6 = 1. Đây là chênh lệch 
 nhỏ nhất có thể phân chia được. 
Ý tưởng thuật toán: Độ phức tạp thuật toán: O(nlogn) 
- Sử dụng mảng f tính tổng tiền tố 
- Sử dụng tìm kiếm nhị phân trên mảng f, do mảng f tăng dần (giá trị Ai dương) để 
tìm điểm g để chia thành 2 phần. Phần 1 tổng s1, phần 2 tổng s2 tính giá trị nhỏ 
nhất của hiệu s1 và s2 đồng thời ta cập nhật giá trị min hiệu đó, nếu tổng s1 < tổng 
s2 tìm g bên phải trên đoạn [g+1, c] ngược lại tìm bên trái đoạn [d, g-1] để tổng s1 
và s2 gần bằng nhau hơn. 
Link test tham khảo: 
https://drive.google.com/drive/u/0/folders/1nw3Jk9qjm7DgNxG5_xyHzNd0EAFK
BAiL 
 13 
 Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 
 15 
 Độ phức tạp thuật toán: O(nlogn) 
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 
Link test tham khảo: 
https://drive.google.com/drive/u/0/folders/10yxrCYNVDqPSaqZANzhato-
mMMMjFD9p 
2.3. DẠNG 2. Tìm kiếm nhị phân theo kết quả 
 Dạng tìm một phần tử trên dãy được sắp xếp là dạng cơ bản quen thuộc. Ta có 
thể mở rộng việc tìm kiếm nhị phân trên miền kết quả. Bắt đầu bằng miền tìm kiếm 
là miền giá trị mà chắc chắn kết quả cần tìm sẽ thuộc vào đó. Với mỗi lần tìm 
kiếm, chia đôi miền đó. Gọi x là giá trị trên miền đó mà cần kiểm tra. 
Xây dựng hàm check(x) trả về true nếu kết quả của x là có thể, ngược lại trả về 
false. Dạng bài toán này, thường tìm giá trị lớn nhất, nhỏ nhất. 
 17 
Link test tham khảo: 
https://drive.google.com/drive/u/0/folders/19L410YFXopgV8qgyGt5X0AVsz5o0
By9M 
Câu 2: Xâu con phân biệt (Nguồn Đề hsg 12 vĩnh phúc 2021) 
 Một lần Mr. Bean được bạn gái gửi cho một dãy ký tự độ dài chỉ gồm các 
chữ cái in hoa (‘A’...’Z’). Bạn gái nhờ Mr. Bean xác định "Độ phân biệt" của dãy 
ký tự trên. Trong đó Độ phân biệt của dãy ký tự là số nguyên dương l nhỏ nhất sao 
cho tất cả các xâu con của S độ dài l là đôi một phân biệt. 
 Chẳng hạn với = 7; = 'ABCDABC' thì l = 4 do tất cả các xâu con độ dài 4 
đều phân biệt. Bạn hãy giúp Mr. Bean việc đó. 
Dữ liệu: 
 ● Dòng 1: số nguyên dương ( ≤ 100). 
 ● Dòng 2: chứa xâu ký tự 
Kết quả: 
 ● Gồm một dòng duy nhất ghi một số nguyên duy nhất là "Độ phân biệt" của 
dãy ký tự . Ví dụ: 
 DIFFSSTR.INP DIFFSSTR.OUT 
 7 4 
 ABCDABC 
Bài toán này có thể sử dụng 2 vòng lặp for kết hợp cấu trúc dữ liệu set, map để xác 
định các đoạn con phân biệt, ngoài ra sử dụng thuật toán đếm phân phối nữa. Dưới 
đây tôi đưa ra giải pháp bằng tìm kiếm nhị phân. 
Ý tưởng thuật toán: Sử dụng chặt nhị phân tìm kết quả 
 - Kết quả bài toán thuộc đoạn [1, n] 
 19 
 Yêu cầu: Xác định độ dài lớn nhất của đoạn dây có thể nhận được. 
Dữ liệu: Vào từ file văn bản CATDAY.INP gồm nhiều dòng: 
 ● Dòng thứ nhất chứa hai số nguyên N và M (1 ≤ N, M ≤ 105) 
 9
 ● Dòng thứ i trong N dòng tiếp theo là số Di (0 < Di ≤ 10 ) 
 Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản DAYDAN.OUT một số nguyên duy nhất là độ dài 
lớn nhất của đoạn dây nhận được. Nếu không có cách cắt thì đưa ra số 0. 
 CATDAY .INP CATDAY .OUT 
 3 2 250 
 100 
 20 
 500 
Ràng buộc: 50% số test ứng với 50% số điểm của bài có 1 ≤ N, M ≤ 100 
Ý tưởng thuật toán: Sử dụng chặt nhị phân tìm kết quả 
 - Kết quả bài toán thuộc đoạn [1, max(ai)] 
 - Gọi g là độ dài đoạn dây cần cắt để có M đoạn bằng nhau. Nếu kiểm tra g 
 thỏa mãn điều kiện bài toán thì tìm bên phải để tìm đoạn độ dài g dài hơn thỏa 
 mãn trên đoạn [g+1, c] ngược lại tìm bên trái đoạn [d, g-1] 
 - Hàm check sử dụng đoạn có độ dài g có thỏa mãn điều kiện bài toán không 
 nếu thỏa mãn trả về true ngược lại false. Cụ thể hơn ta duyệt qua tất cả các 
 phần tử trong mảng đếm số lượng ta cần cắt độ dài g bằng cách lấy a[i]/g nếu 
 số lượng bằng nhau lớn hơn k thì thỏa mãn ngược lại không thỏa mãn. 
Độ phức tạp thuật toán: O(nlogmax(ai)) 
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 
 21