Luyện Tập Tìm Kiếm Nhị Phân
2024 C2A3 - Python cơ bản
Tìm kiếm Nhị phân (Binary Search)
1. Định nghĩa
Tìm kiếm nhị phân là thuật toán tìm kiếm nhanh, sử dụng chiến lược chia đôi danh sách (hoặc mảng) đã được sắp xếp để tìm giá trị cần tìm. Thuật toán này giảm kích thước phạm vi tìm kiếm xuống một nửa sau mỗi bước.
2. Nguyên tắc hoạt động
- Xác định vị trí giữa: Chọn phần tử ở giữa danh sách hiện tại.
- So sánh giá trị cần tìm:
Nếu giá trị giữa bằng giá trị cần tìm, trả về vị trí (chỉ số) của nó.
Nếu giá trị cần tìm nhỏ hơn giá trị giữa, tiếp tục tìm kiếm trong nửa bên trái.
Nếu giá trị cần tìm lớn hơn giá trị giữa, tiếp tục tìm kiếm trong nửa bên phải. - Lặp lại cho đến khi tìm thấy giá trị hoặc danh sách không còn phần tử để kiểm tra.
Ví dụ
- Cho 1 bài toán như sau: Cho trước dãy \(A\) được sắp xếp tăng dần, các phần tử có giá trị phân biệt. Tìm và trả về vị trí của giá trị \(x\).
- Giả sử cho dãy \(A\) \(=\) [\(0\), \(5\), \(13\), \(19\), \(22\), \(41\), \(55\), \(68\), \(72\), \(81\), \(98\)]
- Giả sử ta đi tìm giá trị \(55\) ở vị trí bao nhiêu.
3. Điều kiện áp dụng
- Dữ liệu phải được sắp xếp trước khi thực hiện tìm kiếm nhị phân.
- Phải có cách truy cập phần tử thông qua chỉ số (danh sách hoặc mảng).
4. Thuật toán và Ví dụ minh họa
4.1. Phiên bản lặp
Python
def tim_kiem_nhi_phan(danh_sach, gia_tri_tim):
trai = 0 # Chỉ số đầu tiên
phai = len(danh_sach) - 1 # Chỉ số cuối cùng
while trai <= phai: # Lặp khi vẫn còn phạm vi tìm kiếm
giua = (trai + phai) // 2 # Tìm vị trí giữa
if danh_sach[giua] == gia_tri_tim: # Nếu tìm thấy
return giua
elif danh_sach[giua] < gia_tri_tim: # Nếu giá trị ở giữa nhỏ hơn
trai = giua + 1 # Chuyển sang nửa bên phải
else: # Nếu giá trị ở giữa lớn hơn
phai = giua - 1 # Chuyển sang nửa bên trái
return -1 # Không tìm thấy giá trị
Ví dụ minh họa:
Python
danh_sach = [2, 3, 5, 7, 11, 13, 17, 19]
gia_tri_tim = 7
ket_qua = tim_kiem_nhi_phan(danh_sach, gia_tri_tim)
print(ket_qua) # Kết quả: 3 (giá trị 7 nằm tại chỉ số 3)
4.2. Phiên bản đệ quy
Python
def tim_kiem_nhi_phan_de_quy(danh_sach, trai, phai, gia_tri_tim):
if trai > phai: # Khi phạm vi tìm kiếm không còn
return -1
giua = (trai + phai) // 2 # Tìm vị trí giữa
if danh_sach[giua] == gia_tri_tim: # Nếu tìm thấy
return giua
elif danh_sach[giua] < gia_tri_tim: # Nếu giá trị ở giữa nhỏ hơn
return tim_kiem_nhi_phan_de_quy(danh_sach, giua + 1, phai, gia_tri_tim) # Tìm nửa bên phải
else: # Nếu giá trị ở giữa lớn hơn
return tim_kiem_nhi_phan_de_quy(danh_sach, trai, giua - 1, gia_tri_tim) # Tìm nửa bên trái
Ví dụ minh họa:
Python
danh_sach = [2, 3, 5, 7, 11, 13, 17, 19]
gia_tri_tim = 7
ket_qua = tim_kiem_nhi_phan_de_quy(danh_sach, 0, len(danh_sach) - 1, gia_tri_tim)
print(ket_qua) # Kết quả: 3
Bài tập
| Bài tập | Điểm | Tỷ lệ AC | Người nộp | |
|---|---|---|---|---|
| Khẩu trang | 200p | 29,6% | 1322 | |
| Tìm số trong mảng | 100p | 40,4% | 2639 | |
| Nhỏ hơn | 200p | 24,5% | 1025 | Hướng dẫn |
Bình luận