So sánh số bước và đo thời gian tìm kiếm

Với tìm nhị phân, mỗi lần chưa thấy K đều bỏ phần tử giữa và một nửa không phù hợp. Phần miền còn lại có kích thước không quá một nửa ban đầu. Nếu n=$2^k$, sau khoảng k lần thu nhỏ chỉ còn tối đa một phần tử; số lần xét tăng theo k, tức theo $\log_2 n$. Vì vậy bậc thời gian trong trường hợp xấu nhất là $O(\log n)$, còn tìm tuần tự có thể phải xét cả n phần tử, bậc $O(n)$. Tìm thấy ngay ở giữa vẫn có thể chỉ cần một lần xét; không phải mọi lần tìm đều dùng số bước lớn nhất. Ví dụ với 64 phần tử, khi K lớn hơn mọi phần tử, kích thước các miền không rỗng lần lượt là 64,32,16,8,4,2,1: có 7 lần xét phần tử giữa, rồi một lời gọi miền rỗng. Đang đếm **lần xét phần tử giữa**, không gộp mọi phép tính hoặc lời gọi thành cùng một đơn vị.

Thời gian thực còn phụ thuộc máy, cách cài đặt, dữ liệu và vị trí của K. Muốn so sánh riêng thao tác tìm kiếm, tạo sẵn cùng dãy đã sắp xếp cho cả hai, dùng cùng K và đặt bước tạo/sắp xếp ngoài đoạn đo. Nếu cần đánh giá cả việc chuẩn bị dãy từ dữ liệu chưa sắp xếp, phải tính thêm thời gian ấy và nói rõ phạm vi khác. Kết luận O(log n) của thao tác tìm nhị phân không tự bao gồm chi phí sắp xếp đầu vào.

Chạy mã thực hành: ```text python3 g11-cs-chia-de-tri.py do --repeat 5000 ``` Mã dùng perf_counter, với n=10,20,50,100. Mỗi dãy tạo trước là [0,1,...,n−1], K=n không có trong dãy. Hai thuật toán tìm trên cùng dữ liệu; mỗi phép tìm được lặp 5000 lần để lấy thời gian trung bình mỗi lần, đơn vị mili giây. Đầu ra có tiêu đề `n,tuan_tu_ms_moi_lan,nhi_phan_ms_moi_lan` và bốn dòng số liệu. Ghi bảng, chạy lại và quan sát độ dao động. Thời gian có thể thay đổi giữa các lần chạy; với dãy nhỏ, một mẫu đo chưa đủ để kết luận thuật toán nào luôn nhanh hơn. Bậc O(log n) mô tả cách số thao tác tăng khi quy mô lớn, không ấn định một thời gian đo cố định.