So sánh
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 lũy thừa

Tìm kiếm lũy thừa

Tìm kiếm lũy thừa tìm một giá trị trong danh sách đã sắp xếp qua hai giai đoạn. Đầu tiên, nó xem các vị trí 1, 2, 4, 8, 16, v.v., mỗi lần gấp đôi, cho đến khi giá trị ở đó không nhỏ hơn mục tiêu. Sau đó, nó tìm kiếm nhị phân trên đoạn giữa hai vị trí cuối. Chọn giá trị cần tìm và xem vì sao các mục tiêu gần đầu được tìm thấy chỉ sau vài phép so sánh. 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 lũy thừa 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

  1. Chọn giá trị cần tìm và số cột. Hoặc tự nhập các số: tìm kiếm lũy thừa 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. Tìm một giá trị gần đầu và một giá trị gần cuối, rồi so số lần với ô Tìm kiếm nhị phân cần.

Cách tìm kiếm lũy thừa hoạt động

Xem giá trị ở vị trí 1. Nếu nó nhỏ hơn mục tiêu, xem vị trí 2, rồi 4, 8, 16, mỗi lần gấp đôi. Ngay khi một giá trị không nhỏ hơn, dừng lại: mục tiêu chỉ có thể nằm sau vị trí đã xem trước đó và trước vị trí này. Tìm kiếm nhị phân trên đoạn đó. Nếu việc gấp đôi vượt quá cuối danh sách, tìm kiếm nhị phân từ vị trí cuối cùng đã xem đến hết danh sách.

Nhanh khi gần đầu, không cần biết độ dài

Để đến mục tiêu ở vị trí i, việc gấp đôi cần khoảng log₂ i lần xem, và đoạn tìm được chứa ít hơn i giá trị, nên tìm kiếm nhị phân cần thêm khoảng log₂ i lần nữa. Tổng cộng khoảng 2 log₂ i, phụ thuộc vào vị trí của mục tiêu chứ không phải độ dài danh sách. Mục tiêu gần đầu được tìm thấy nhanh hơn so với tìm kiếm nhị phân thông thường; mục tiêu gần cuối tốn đến khoảng gấp đôi. Vì không bao giờ cần độ dài danh sách, nó cũng dùng được với danh sách quá dài để đo hoặc không biết điểm kết thúc.

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

Tìm kiếm lũy thừa hoạt động thế nào?

Trên danh sách đã sắp xếp, nó kiểm tra các vị trí 1, 2, 4, 8, v.v. cho đến khi giá trị ở đó không nhỏ hơn mục tiêu. Khi đó mục tiêu chỉ có thể nằm giữa hai vị trí kiểm tra cuối cùng, và tìm kiếm nhị phân trên đoạn đó sẽ tìm ra nó.

Tìm kiếm lũy thừa có nhanh hơn tìm kiếm nhị phân không?

Khi mục tiêu gần đầu danh sách thì có: nó cần khoảng 2 log₂ i phép so sánh cho mục tiêu ở vị trí i, bất kể độ dài danh sách. Khi mục tiêu gần cuối, tìm kiếm nhị phân thông thường nhanh hơn, đến khoảng gấp đôi.

Nó được dùng để làm gì?

Tìm trong danh sách không biết độ dài hoặc không giới hạn, như một luồng dữ liệu hay một dãy vô hạn, và trộn các dãy con đã sắp xếp, nơi giá trị khớp tiếp theo thường ở gần. Chế độ galloping của Timsort dùng cùng ý tưởng gấp đôi này.

Vì sao gọi là lũy thừa?

Vì các vị trí nó kiểm tra tăng theo lũy thừa: 1, 2, 4, 8, 16, mỗi vị trí gấp đôi vị trí trước. Nó còn được gọi là doubling search hay galloping search.

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