Trình trực quan hóa tìm kiếm nhị phân

Cách dùng

1. 1 Đặt một giá trị Target (mảng luôn được tự động sắp xếp để phục vụ tìm kiếm nhị phân).
2. 2 Nhấn Play để xem quá trình tìm kiếm chia đôi phạm vi ở mỗi bước, hoặc dùng Step để chạy từng bước một.
3. 3 Nhập các số của riêng bạn vào ô Custom rồi nhấn Apply — chúng sẽ được sắp xếp lại.
4. 4 Theo dõi pseudocode được tô sáng cùng phạm vi lo / mid / hi khi nó thu hẹp dần.

Vì sao dùng công cụ này

• Xem cách mỗi lần so sánh loại bỏ một nửa số phần tử còn lại.
• Hiểu vì sao tìm kiếm nhị phân có độ phức tạp O(log n) — phạm vi tìm kiếm thu hẹp theo cấp số nhân.
• Quan sát vùng bị làm mờ mở rộng dần khi các ứng viên bị loại bỏ.
• Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải lên.

Câu hỏi thường gặp

Trình trực quan hóa tìm kiếm nhị phân là gì?

Trình trực quan hóa tìm kiếm nhị phân mô phỏng cách thuật toán tìm kiếm nhị phân xác định vị trí một giá trị mục tiêu trong mảng đã sắp xếp, bằng cách liên tục so sánh phần tử ở giữa và loại bỏ nửa mảng chắc chắn không chứa mục tiêu. Công cụ hiển thị phạm vi lo–hi thu hẹp dần và số lần so sánh, cho thấy vì sao tìm kiếm nhị phân có độ phức tạp O(log n).

Tính năng

Ví dụ

find 7 in [1, 3, 5, 7, 9, 11]

mid=5 → mid=9 → mid=7 → found at index 3

Trường hợp sử dụng

1. 1

   Hiểu tìm kiếm logarit

   Xem lý do vì sao việc chia đôi phạm vi lại cho ra thời gian tra cứu O(log n).

2. 2

   Tra cứu dữ liệu đã sắp xếp

   Tìm hiểu khi nào tìm kiếm nhị phân vượt trội hơn quét tuyến tính.

3. 3

   Gỡ lỗi sai lệch ranh giới (off-by-one)

   Theo dõi cách low/high/mid di chuyển để tránh lỗi ranh giới.

Tài liệu tham khảo

• MIT OCW 6.006 — Nhập môn Thuật toán (CLRS) — MIT OpenCourseWare
• Thuật toán tìm kiếm nhị phân — Wikipedia

Công cụ liên quan