Lần dò
Còn khả năng
Tìm kiếm nhị phân cần

  • Mục tiêu
  • Còn khả năng
  • Đang so sánh
  • Đã loại
  • Đã tìm thấy

Tìm hiểu thêm về tìm kiếm nội suy

Tìm kiếm nội suy

Tìm kiếm nội suy tìm một giá trị trong danh sách đã sắp xếp giống như cách bạn mở danh bạ điện thoại: để tìm tên bắt đầu bằng T, bạn mở gần cuối chứ không mở ở giữa. Nó ước tính vị trí của mục tiêu từ giá trị ở hai đầu của phần còn lại. Chọn giá trị và cách phân bố các giá trị, đi qua từng lần dò, và xem khi nào ước tính thắng tìm kiếm nhị phân, khi nào không. 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 nội suy 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ị, cách phân bố các 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

  1. Chọn giá trị cần tìm, cách phân bố các giá trị và số cột. Hoặc tự nhập các số: tìm kiếm nội suy sẽ sắp xếp chúng trước.
  2. 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.
  3. Chuyển Phân bố giữa Đều, Khoảng cách ngẫu nhiên và Lệch, rồi so sánh Lần dò với Tìm kiếm nhị phân cần.

Cách tìm kiếm nội suy hoạt động

Xem giá trị đầu và cuối của phần danh sách đã sắp xếp vẫn có thể chứa mục tiêu. Nếu mục tiêu nằm, chẳng hạn, ở 40% quãng từ giá trị đầu đến giá trị cuối, hãy dò vị trí ở 40% chiều dài phần đó. Nếu giá trị ở đó là mục tiêu, bạn đã xong. Nếu nó nhỏ hơn, chỉ còn các vị trí sau nó; nếu lớn hơn, chỉ còn các vị trí trước nó. Ước tính lại trong phần còn lại. Nếu mục tiêu nhỏ hơn giá trị đầu hoặc lớn hơn giá trị cuối, nó không có ở đó.

Khi nào ước tính hiệu quả

Nếu các giá trị phân bố đều, như 10, 20, 30, v.v., ước tính đầu tiên rơi trúng mục tiêu hoặc rất gần, và trung bình cần khoảng log₂(log₂ n) lần dò: khoảng 5 với một tỷ giá trị, so với 30 của tìm kiếm nhị phân. Nếu các giá trị dồn cục, như 1, 2, 3, 4, 1000, ước tính cứ rơi sai chỗ và mỗi lần dò có thể chỉ loại được một giá trị, nên trường hợp xấu nhất là n lần dò. Tìm kiếm nhị phân không bao giờ tệ hơn khoảng log₂ n.

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

Tìm kiếm nội suy hoạt động thế nào?

Trên danh sách đã sắp xếp, nó ước tính vị trí mục tiêu từ giá trị đầu và cuối của phần còn lại, dò vị trí đó và chỉ giữ phần ở phía đúng. Nó giống tìm kiếm nhị phân nhưng đoán thông minh hơn là lấy điểm giữa.

Tìm kiếm nội suy có nhanh hơn tìm kiếm nhị phân không?

Với các giá trị phân bố đều thì có: trung bình khoảng log₂(log₂ n) lần dò thay vì khoảng log₂ n. Với các giá trị phân bố không đều, nó có thể chậm hơn nhiều, tới n lần dò, trong khi tìm kiếm nhị phân không bao giờ cần quá khoảng log₂ n.

Vì sao nó có thể chậm?

Vì ước tính giả định các giá trị tăng đều. Nếu phần lớn giá trị nhỏ và một vài giá trị rất lớn, ước tính cho mục tiêu nhỏ cứ rơi gần đầu danh sách và mỗi lần chỉ loại được một hai giá trị.

Tìm kiếm nội suy được dùng ở đâu?

Ở nơi khóa phân bố gần đều và mỗi lần dò tốn kém, chẳng hạn tra cứu bản ghi theo ID số hoặc giá trị băm trên đĩa. Nhiều hệ thống kết hợp nó với tìm kiếm nhị phân để giữ trường hợp xấu nhất ở mức tốt.

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