Khái niệm
Tìm kiếm nhị phân (binary search) hoạt động trên dãy đã được sắp xếp. Mỗi bước loại bỏ một nửa phần tử còn lại bằng cách so sánh phần tử giữa với giá trị cần tìm.
- Điều kiện tiên quyết: Dãy phải được sắp xếp tăng dần (hoặc giảm dần).
- Độ phức tạp thời gian: O(log n) — mỗi bước loại nửa phần tử
- Độ phức tạp không gian: O(1)
Với n = 10⁶, tìm kiếm tuyến tính cần đến 10⁶ bước; tìm kiếm nhị phân chỉ cần tối đa 20 bước.
Sơ đồ luồng
Cài đặt cơ bản
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1 # target ở nửa phải
else:
hi = mid - 1 # target ở nửa trái
return -1
numbers = [1, 3, 5, 7, 9, 11, 15, 20]
print(binary_search(numbers, 7)) # 3
print(binary_search(numbers, 6)) # -1
print(binary_search(numbers, 1)) # 0
print(binary_search(numbers, 20)) # 7
Dạng mở rộng
Tìm vị trí chèn (lower bound)
Tìm vị trí nhỏ nhất để chèn target vào mà dãy vẫn còn sắp tăng.
def lower_bound(arr, target):
"""Trả về vị trí đầu tiên có giá trị >= target."""
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
arr = [1, 3, 3, 5, 7]
print(lower_bound(arr, 3)) # 1 (vị trí đầu tiên có 3)
print(lower_bound(arr, 4)) # 3 (vị trí đầu tiên có giá trị >= 4)
print(lower_bound(arr, 8)) # 5 (chèn vào cuối)
# Có thể dùng bisect từ thư viện chuẩn
import bisect
print(bisect.bisect_left(arr, 3)) # 1
print(bisect.bisect_right(arr, 3)) # 3 (vị trí sau tất cả số 3)
Bài tập luyện tập
Dễ — Kiểm tra phần tử tồn tại
def ton_tai(arr, target):
"""Kiểm tra xem target có trong dãy đã sắp xếp không."""
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return False
sorted_data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(ton_tai(sorted_data, 23)) # True
print(ton_tai(sorted_data, 10)) # False
Trung bình — Đếm số lần xuất hiện
Cho dãy đã sắp xếp, đếm số lần xuất hiện của target trong O(log n).
import bisect
def dem_xuat_hien(arr, target):
"""Đếm số lần target xuất hiện trong dãy đã sắp xếp."""
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 4, 5, 5]
print(dem_xuat_hien(arr, 2)) # 3
print(dem_xuat_hien(arr, 5)) # 2
print(dem_xuat_hien(arr, 6)) # 0
Khó — Tìm kiếm nhị phân trên hàm số (Binary search on answer)
Bài toán: Tìm số nguyên nhỏ nhất x sao cho x² >= n. Đây là kỹ thuật “tìm kiếm nhị phân trên đáp án” — không tìm trong mảng mà tìm giá trị thoả điều kiện trong một khoảng.
def can_bac_hai_tran(n):
"""Tìm số nguyên nhỏ nhất x sao cho x*x >= n."""
if n <= 0:
return 0
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
if mid * mid >= n:
hi = mid
else:
lo = mid + 1
return lo
print(can_bac_hai_tran(16)) # 4 (4*4 = 16)
print(can_bac_hai_tran(17)) # 5 (4*4=16<17, 5*5=25>=17)
print(can_bac_hai_tran(1)) # 1
print(can_bac_hai_tran(100)) # 10
Nâng cao — Tìm kiếm nhị phân trong dãy xoay
Dãy đã sắp xếp bị xoay tại một vị trí nào đó (ví dụ: [4,5,6,7,0,1,2]). Tìm vị trí của target trong O(log n).
def tim_trong_day_xoay(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
# Kiểm tra nửa nào đang sắp xếp đúng thứ tự
if arr[lo] <= arr[mid]: # Nửa trái đã sắp xếp
if arr[lo] <= target < arr[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # Nửa phải đã sắp xếp
if arr[mid] < target <= arr[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
arr = [4, 5, 6, 7, 0, 1, 2]
print(tim_trong_day_xoay(arr, 0)) # 4
print(tim_trong_day_xoay(arr, 5)) # 1
print(tim_trong_day_xoay(arr, 3)) # -1
Kết luận
Tìm kiếm nhị phân có thể áp dụng cho mọi bài toán có tính đơn điệu (monotonic): nếu x thoả điều kiện thì x+1 cũng thoả (hoặc ngược lại). Kỹ thuật “binary search on answer” là một công cụ mạnh để giải nhiều bài tối ưu hóa trong thi đấu.
Bình luận