Bài giảng được trình bày theo hướng hiện đại, ngắn gọn, dễ hiểu: nắm ý tưởng, nhận biết dạng bài, dùng hàm thư viện và luyện bài tập có ví dụ.
Cho một dãy gồm n đối tượng, mỗi đối tượng có một khóa tìm kiếm. Cần xác định có đối tượng nào có khóa bằng giá trị k hay không.
Tìm kiếm tuần tự có thể phải duyệt hết dãy, độ phức tạp thường là O(n).
Tìm kiếm nhị phân chỉ dùng được khi không gian tìm kiếm có thứ tự, thường là dãy đã được sắp xếp tăng hoặc giảm.
Độ phức tạp tìm kiếm là O(log n). Nếu phải sắp xếp trước thì cần tính thêm chi phí sắp xếp.
Giả sử dãy tăng dần. Tại mỗi bước, xét phần tử giữa mid:
binary_search(a, x): left = 1, right = n while left <= right: mid = (left + right) / 2 if a[mid] == x: return true if a[mid] < x: left = mid + 1 else: right = mid - 1 return false
| Hàm | Ý nghĩa | Ghi nhớ nhanh |
|---|---|---|
| binary_search(first,last,x) | Kiểm tra x có tồn tại trong đoạn đã sắp xếp hay không. | Trả về true / false. |
| lower_bound(first,last,x) | Tìm vị trí đầu tiên có giá trị không nhỏ hơn x. | Đầu tiên ≥ x. |
| upper_bound(first,last,x) | Tìm vị trí đầu tiên có giá trị lớn hơn x. | Đầu tiên > x. |
| equal_range(first,last,x) | Trả về đoạn chứa các phần tử bằng x. | Dùng để kiểm tra hoặc đếm số lần xuất hiện. |
Dùng upper_bound để tìm phần tử đầu tiên lớn hơn x, sau đó lùi lại một vị trí.
3 5 10 11 13 18 18 25 27 31
Vị trí: 7 Giá trị: 18
Dùng lower_bound để tìm phần tử đầu tiên không nhỏ hơn x.
1 2 4 4 6 9 10
Vị trí đầu tiên ≥ 4: 3
Chặt nhị phân không chỉ dùng để tìm trong mảng. Nó còn dùng để tìm kết quả nhỏ nhất hoặc lớn nhất thỏa mãn điều kiện, miễn là ta xây dựng được hàm kiểm tra P(x) có tính đơn điệu.
res = -1
while left <= right:
mid = (left + right) / 2
if P(mid) == true:
res = mid
right = mid - 1
else:
left = mid + 1res = -1
while left <= right:
mid = (left + right) / 2
if P(mid) == true:
res = mid
left = mid + 1
else:
right = mid - 1| Bài | Tên bài | Kỹ năng chính | Mức độ |
|---|---|---|---|
| 1 | Kiểm tra tồn tại | binary_search | Dễ |
| 2 | Đếm số lần xuất hiện | lower_bound / upper_bound | Dễ |
| 3 | Phần tử gần nhất ≤ x | upper_bound | Trung bình |
| 4 | Phần tử gần nhất ≥ x | lower_bound | Trung bình |
| 5 | Số chính phương thiếu | Sắp xếp + tìm kiếm nhị phân | Trung bình |
| 6 | Căn bậc hai nguyên | Chặt nhị phân kết quả | Trung bình |
| 7 | Cắt dây | Tìm giá trị lớn nhất thỏa điều kiện | Khá |
| 8 | Chia sách | Tìm giá trị nhỏ nhất thỏa điều kiện | Khá |
| 9 | Tìm căn số thực | Nhị phân trên số thực | Trung bình |
| 10 | Khoảng cách router | Binary search on answer | Khá |
Cho dãy số nguyên gồm n phần tử và q truy vấn. Mỗi truy vấn cho một số nguyên x. Hãy cho biết x có xuất hiện trong dãy hay không.
6 4 1 8 3 3 10 5 3 2 10 7
YES NO YES NO
Cho dãy số nguyên gồm n phần tử và q truy vấn. Với mỗi truy vấn x, hãy in ra số lần x xuất hiện trong dãy.
8 3 1 2 2 2 5 5 9 10 2 5 4
3 2 0
Cho dãy số đã sắp xếp tăng dần. Với mỗi truy vấn x, hãy tìm vị trí lớn nhất của phần tử có giá trị ≤ x. Nếu không tồn tại, in -1.
10 3 3 5 10 11 13 18 18 25 27 31 20 2 18
7 -1 7
Cho dãy số đã sắp xếp tăng dần. Với mỗi truy vấn x, hãy tìm vị trí nhỏ nhất của phần tử có giá trị ≥ x. Nếu không tồn tại, in -1.
7 4 1 2 4 4 6 9 10 4 5 11 0
3 5 -1 1
Cho dãy số nguyên dương a gồm n phần tử. Hãy tìm số chính phương nhỏ nhất không xuất hiện trong dãy.
7 1 4 9 16 25 36 49
0
Cho số nguyên dương n. Hãy tìm số nguyên x lớn nhất sao cho x² ≤ n.
30
5
Có n đoạn dây, đoạn thứ i dài a[i]. Cần cắt thành ít nhất k đoạn dây bằng nhau có độ dài nguyên. Tìm độ dài lớn nhất có thể.
4 11 802 743 457 539
200
Có n quyển sách theo thứ tự, quyển i có a[i] trang. Chia cho k học sinh, mỗi học sinh nhận một đoạn liên tiếp các quyển sách. Hãy tối thiểu hóa số trang nhiều nhất mà một học sinh phải đọc.
4 2 12 34 67 90
113
Cho số thực dương n. Hãy tính căn bậc hai của n với độ chính xác 6 chữ số thập phân.
2
1.414214
Có n vị trí trên một đường thẳng. Cần đặt k router vào k vị trí khác nhau sao cho khoảng cách nhỏ nhất giữa hai router bất kỳ là lớn nhất.
5 3 1 2 8 4 9
3