Loại phần không còn phù hợp
A đã sắp xếp **không giảm**. Hàm tìm K trong đoạn chỉ số [left,right], gồm cả hai đầu. Khi có phần tử, lấy mid ở giữa; nếu A[mid]==K thì trả mid. Nếu A[mid]<K, chỉ tìm bên phải; nếu A[mid]>K, chỉ tìm bên trái.
Chia: tách miền qua phần tử giữa. Trị: giải nhánh còn có khả năng chứa K. Kết hợp: trả kết quả của nhánh ấy về nơi gọi. Do tính chất dãy đã sắp xếp, không cần giải cả hai nhánh rồi ghép hai kết quả.
Cơ sở được kiểm trước khi đọc phần tử
```python
def binarySearch(A, left, right, K):
if left > right:
return -1
mid = (left + right) // 2
if A[mid] == K:
return mid
if A[mid] < K:
return binarySearch(A, mid + 1, right, K)
return binarySearch(A, left, mid - 1, K)
```
Gọi đầu với left=0, right=len(A)−1. Miền rỗng trả −1. Khi left==right, vẫn phải đọc và so sánh phần tử duy nhất; nếu khác K thì lời gọi tiếp tạo miền rỗng. Nếu nhiều phần tử bằng K, hàm chỉ cần trả một chỉ số phù hợp, không hứa trả vị trí đầu tiên.
So sánh giá trị, không so sánh chỉ số với K
Với A=[100,200,300] và K=100, lần đầu mid=1 nhưng A[mid]=200. Vì 200>100, chọn miền [0,0]; phần tử duy nhất bằng K nên trả 0.
Không dùng mid<K để quyết định nhánh: chỉ số 1 và giá trị 100 là hai đại lượng khác nhau. Return trước lời gọi nhỏ chuyển chỉ số tìm được về lời gọi ban đầu.
Bản dùng vòng lặp cũng có thể liên tục cập nhật left/right theo cùng cách chia miền; cách viết không đệ quy vẫn giữ ý tưởng chia để trị của thuật toán.
Bài luyện
Với A=[100,200,300], K=100, ở lần đầu cần dùng phép so sánh nào để chọn nhánh?
Nhánh phụ thuộc giá trị phần tử giữa và giá trị cần tìm.
Chỉ số không phải giá trị đang tìm.
Độ dài chưa cho biết K nằm ở phía nào.
Còn phải dùng dữ liệu ở phần tử giữa.
Lời giải
mid=(0+2)//2=1. Vì A[1]=200>K=100, thuật toán tìm tiếp bên trái ở [0,0] và tìm thấy chỉ số 0.
Bài luyện
Tìm K=5 trên A=[7] bằng hàm trong bài. Điều gì xảy ra?
Quy ước đầu ra là chỉ số hoặc −1.
Phần tử duy nhất khác K nên chưa tìm thấy.
Một phần tử chưa chắc là phần tử cần tìm.
Miền gồm một phần tử vẫn cần được xét.
Lời giải
Ban đầu left=right=0, mid=0 và A[0]=7>5. Lời gọi tiếp có left=0,right=−1, nên nhánh miền rỗng trả −1.
Bài luyện
Trong cách giải này, bước kết hợp được thực hiện như thế nào?
Không có thao tác ghép dãy trong chương trình.
Kết quả nhánh nhỏ đã đủ theo phần miền còn lại.
Chỉ một nhánh cần được giải sau phép so sánh.
Thuật toán không tìm đồng thời cả hai nửa và không cộng chỉ số.
Lời giải
Phép so sánh đã loại nửa không thể chứa K. Lời gọi nhỏ trả một chỉ số phù hợp hoặc −1; return chuyển nguyên kết quả đó về bài toán ban đầu.
Bài luyện
Viết tìm kiếm nhị phân bằng vòng lặp, vẫn chia miền và chỉ giữ nửa phù hợp. Nhận xét nào đúng?
Đệ quy là cách cài đặt, không phải điều kiện duy nhất của ý tưởng.
Căn cứ loại một nửa vẫn cần thứ tự của dãy.
Chỉ cần nửa còn có khả năng chứa K.
Cách chia và giải phần nhỏ còn giữ nguyên.
Lời giải
Vòng lặp cập nhật miền thay cho lời gọi hàm, nhưng vẫn thu nhỏ bài toán theo cùng phép so sánh với phần tử giữa. Vì vậy ý tưởng chia để trị của tìm nhị phân vẫn được giữ.
Đang học