- Mục tiêu
- Còn khả năng
- Đang so sánh
- Đã loại
- Đã tìm thấy
Tìm kiếm nhị phân
Tìm kiếm nhị phân tìm một giá trị trong danh sách đã sắp xếp bằng cách luôn nhìn vào giữa. Nếu giá trị giữa quá nhỏ, giá trị cần tìm chỉ có thể nằm sau nó; nếu quá lớn, chỉ có thể nằm trước. Dù thế nào, một nửa phần còn lại cũng bị loại. Chọn giá trị cần tìm, đi từng bước qua quá trình tìm kiếm, và xem phần tô bóng thu hẹp cho đến khi tìm thấy hoặc không còn gì. Nhấn Phát để xem quá trình tìm kiếm, hoặc Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Đường nét đứt đánh dấu giá trị cần tìm, còn phần tô bóng là nơi nó vẫn có thể nằm. Tìm kiếm nhị phân cần danh sách đã sắp xếp, nên danh sách chưa sắp xếp sẽ được sắp xếp trước. Chọn giá trị, số cột, hoặc tự nhập các số. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chọn giá trị cần tìm và số cột. Hoặc tự nhập các số: tìm kiếm nhị phân sẽ sắp xếp chúng trước.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình tìm kiếm.
- So ô So sánh với ô Tìm kiếm tuyến tính cần, với một giá trị gần cuối hoặc một giá trị không có.
Cách tìm kiếm nhị phân hoạt động
Theo dõi phần của danh sách đã sắp xếp vẫn có thể chứa giá trị cần tìm; lúc đầu đó là cả danh sách. Nhìn giá trị ở giữa phần đó. Nếu bằng giá trị cần tìm là xong. Nếu nhỏ hơn, giá trị cần tìm chỉ có thể nằm sau nó, nên tiếp tục với phần sau giữa. Nếu lớn hơn, tiếp tục với phần trước. Khi không còn gì, giá trị cần tìm không có trong danh sách.
Vì sao nhanh đến vậy
Mỗi phép so sánh chia đôi phần còn lại. Bắt đầu từ n giá trị, sau k phép so sánh còn nhiều nhất khoảng n/2ᵏ, nên việc tìm kiếm kết thúc sau nhiều nhất ⌊log₂ n⌋ + 1 phép so sánh: 6 cho 40 giá trị, 10 cho 1.000, 20 cho một triệu. Tìm kiếm tuyến tính có thể phải xem mọi giá trị. Điều kiện là danh sách phải được sắp xếp, và việc giữ nó luôn sắp xếp, hay sắp xếp trước, cũng có chi phí riêng.
Câu hỏi thường gặp
Tìm kiếm nhị phân hoạt động thế nào?
Nó so sánh giá trị cần tìm với giá trị giữa của phần danh sách đã sắp xếp vẫn có thể chứa nó. Bằng nhau là tìm thấy; nếu không, nửa không thể chứa giá trị cần tìm bị bỏ, và việc tìm tiếp tục ở nửa kia cho đến khi tìm thấy hoặc không còn gì.
Tìm kiếm nhị phân cần bao nhiêu phép so sánh?
Nhiều nhất ⌊log₂ n⌋ + 1 với danh sách n giá trị: 6 cho 40, 10 cho 1.000, 20 cho một triệu. Mỗi phép so sánh chia đôi phần còn lại.
Vì sao tìm kiếm nhị phân cần danh sách đã sắp xếp?
Vì chỉ trong danh sách đã sắp xếp, một phép so sánh mới cho biết giá trị cần tìm nằm ở phía nào. Trong danh sách chưa sắp xếp, giá trị giữa nhỏ hơn không nói gì về vị trí của giá trị cần tìm, nên không loại được gì.
Khi có giá trị trùng, nó tìm thấy giá trị nào?
Một trong số đó, tùy vị trí giữa rơi vào đâu. Các biến thể tiếp tục tìm sang trái hoặc phải sau khi khớp sẽ tìm thấy lần xuất hiện đầu tiên hoặc cuối cùng.
Các số của tôi có bị gửi đi đâu không?
Không. Việc tìm kiếm chạy trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa