Chứng minh tìm kiếm nhị phân bằng bất biến vòng lặp

1. Bắt đầu từ vị trí chèn, rồi mới xét có tìm thấy hay không

Cho dãy a đã sắp không giảm và khóa x. Ta cần tìm chỉ số đầu tiên có a[i] ≥ x. Nếu mọi phần tử nhỏ hơn x, kết quả là len(a). Đây là vị trí chèn đầu tiên để dãy vẫn giữ thứ tự. Từ vị trí đó, chỉ cần kiểm tra thêm i < len(a) và a[i] == x để tìm lần xuất hiện đầu tiên của khóa.

Đặc tả này xử lý thống nhất cả phần tử trùng lặp lẫn mảng rỗng. Với dãy [1, 3, 3, 5] và khóa 3, chỉ số đúng là 1. Với khóa 6, vị trí chèn là 4 và kết quả tìm phần tử là −1. Việc tách hai câu hỏi giúp tránh dùng lẫn chỉ số chèn với chỉ số tồn tại.

2. Chọn bất biến cho khoảng nửa mở

Dùng hai biên lo và hi. Ở đầu mỗi vòng lặp, duy trì ba mệnh đề.

1. 0 ≤ lo ≤ hi ≤ len(a).
2. Mọi vị trí nhỏ hơn lo chứa giá trị nhỏ hơn x.
3. Mọi vị trí từ hi trở đi chứa giá trị lớn hơn hoặc bằng x.

Khi bắt đầu với lo = 0 và hi = len(a), hai vùng đã phân loại đều rỗng. Nếu a[mid] < x, do dãy đã sắp, mọi phần tử từ đầu tới mid đều nhỏ hơn x. Ta đặt lo = mid + 1. Ngược lại, mọi phần tử từ mid trở đi đều lớn hơn hoặc bằng x, nên đặt hi = mid. Cả hai nhánh giữ bất biến.

3. Vì sao vòng lặp dừng và cho đúng vị trí

Khi lo < hi, phép chia nguyên cho lo ≤ mid < hi. Dù chọn nhánh nào, hi − lo giảm nghiêm ngặt và luôn không âm. Khi dừng, lo == hi. Theo bất biến, phía trái điểm đó nhỏ hơn khóa, còn phía phải bắt đầu từ điểm đó lớn hơn hoặc bằng khóa. Điểm gặp nhau chính là kết quả cần tìm.

Ví dụ với a = [1, 3, 3, 5] và x = 3. Ban đầu (lo, hi) = (0, 4). Kiểm tra chỉ số 2 và hạ hi xuống 2. Sau đó kiểm tra chỉ số 1 và hạ hi xuống 1. Cuối cùng, chỉ số 0 có giá trị 1 nên nâng lo lên 1. Thuật toán chọn bản sao đầu tiên của số 3. Với dãy có truy cập theo chỉ số hằng số, số vòng lặp tăng theo O(log n).

4. Kiểm chứng và tạo phản ví dụ cho lỗi thường gặp

"""Tìm vị trí chèn đầu tiên trong một dãy đã sắp không giảm."""
from bisect import bisect_left
from itertools import combinations_with_replacement


def vi_tri_chen(danh_sach, khoa):
    lo, hi = 0, len(danh_sach)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if danh_sach[mid] < khoa:
            lo = mid + 1
        else:
            hi = mid
    return lo


def tim_lan_dau(danh_sach, khoa):
    i = vi_tri_chen(danh_sach, khoa)
    return i if i < len(danh_sach) and danh_sach[i] == khoa else -1


if __name__ == "__main__":
    a = [1, 3, 3, 5]
    for khoa in (0, 3, 4, 6):
        print(khoa, "vị trí chèn:", vi_tri_chen(a, khoa),
              "| vị trí xuất hiện:", tim_lan_dau(a, khoa))

    so_ca = 0
    for n in range(6):
        for day in combinations_with_replacement(range(-2, 3), n):
            for khoa in range(-3, 4):
                expected = bisect_left(day, khoa)
                assert vi_tri_chen(day, khoa) == expected
                assert tim_lan_dau(day, khoa) == next(
                    (i for i, value in enumerate(day) if value == khoa), -1
                )
                so_ca += 1
    print("Đã đối chiếu", so_ca, "ca.")

Chạy python bat_bien_nhi_phan.py. Chương trình sinh mọi dãy không giảm dài từ 0 đến 5 trên một miền nhỏ và đối chiếu với bisect_left. Để xem lỗi dừng, thử đổi lo = mid + 1 thành lo = mid rồi xét dãy [1], khóa 2. Khi biên không đổi, vòng lặp không kết thúc. Cách an toàn khi thử là thêm giới hạn số vòng hoặc lần theo bằng tay.

Tiếp theo, thử sửa nhánh hạ biên thành hi = mid - 1. Tìm một dãy ngắn khiến thuật toán bỏ mất vị trí hợp lệ. Kiểm thử tìm phản ví dụ trong miền đã chạy, còn chứng minh bằng bất biến giải thích vì sao thuật toán đúng với mọi dãy thỏa tiền điều kiện.

Đọc thêm tại Python · bisect_left và phân hoạch dãy.