Tìm kiếm lũy thừa
Tìm kiếm nhị phân cần biết danh sách kết thúc ở đâu trước khi có thể xem ở giữa. Tìm kiếm lũy thừa thì không: nó phi nước đại về phía trước với những bước ngày càng lớn cho đến khi vượt quá mục tiêu, rồi tìm kiếm nhị phân trong bước cuối. Nhờ vậy nó rất hợp với danh sách không biết độ dài, và nhanh với các giá trị gần đầu.
Ý tưởng
Kiểm tra giá trị ở vị trí 1, rồi 2, 4, 8, 16, v.v., mỗi vị trí gấp đôi vị trí trước. Chừng nào giá trị ở đó còn nhỏ hơn mục tiêu, mục tiêu phải nằm xa hơn. Lần đầu tiên một giá trị không nhỏ hơn, mục tiêu đã bị khoanh vùng: nó nằm sau vị trí đã kiểm tra trước đó và không xa hơn vị trí này. Đoạn đó đã được sắp xếp, nên tìm kiếm nhị phân sẽ tìm ra mục tiêu, hoặc cho thấy nó không có.
Ví dụ
Tìm 23 trong 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Vị trí 1 là 2, vị trí 2 là 5, vị trí 4 là 12, đều nhỏ hơn. Vị trí 8 là 56, lớn hơn, nên 23 chỉ có thể ở các vị trí 5 đến 7. Tìm kiếm nhị phân kiểm tra vị trí giữa của chúng, vị trí 6, và tìm thấy 23: 5 phép so sánh, trong khi tìm kiếm nhị phân thông thường cần 3. Tìm 12 trong cùng danh sách thì dừng ở vị trí 4 sau 3 phép so sánh, ít hơn tìm kiếm nhị phân một lần, còn 2 được tìm thấy ở vị trí 1 chỉ với một phép so sánh.
Bao nhiêu phép so sánh
Với mục tiêu ở vị trí i, việc gấp đôi dừng sau khoảng log₂ i bước, và để lại một đoạn ít hơn i vị trí, mà tìm kiếm nhị phân xử lý trong khoảng log₂ i bước nữa. Vậy việc tìm kiếm tốn khoảng 2 log₂ i phép so sánh, bất kể độ dài danh sách. Khi mục tiêu gần đầu, cách này thắng tìm kiếm nhị phân, vốn luôn tốn khoảng log₂ n. Khi mục tiêu gần cuối, tìm kiếm lũy thừa tốn đến khoảng gấp đôi. Với 40 giá trị, ứng dụng trung bình cần khoảng 3 phép so sánh cho năm vị trí đầu và khoảng 9 cho năm vị trí cuối, so với khoảng 4,6 của tìm kiếm nhị phân.
Độ dài không biết trước, và galloping
Jon Bentley và Andrew Yao mô tả chiến lược gấp đôi này vào năm 1976 cho bài toán tìm kiếm không giới hạn: tìm một giá trị trong một dãy đã sắp xếp không biết điểm kết thúc, như một danh sách vô hạn hay một luồng dữ liệu mà bạn chỉ có thể dò từng vị trí. Cùng ý tưởng đó giúp tăng tốc việc trộn. Khi một trong hai dãy con đã sắp xếp liên tục thắng, Timsort chuyển sang chế độ galloping: nó nhìn trước 1, 2, 4, 8 vị trí trong dãy con kia để tìm chỗ cho giá trị tiếp theo, thay vì đi từng vị trí một.
Khám phá
Mở ứng dụng, chọn một giá trị ở mục Tìm, rồi nhấn Bước. Mỗi lần xem vị trí 1, 2, 4, 8, v.v. đều được làm nổi bật; khi một giá trị không nhỏ hơn, đoạn giữa hai vị trí cuối được tô bóng và tìm kiếm nhị phân tiếp quản. Hãy tìm một giá trị nhỏ rồi một giá trị lớn, và so số lần với ô tìm kiếm nhị phân.
Câu hỏi thường gặp
Độ phức tạp thời gian của tìm kiếm lũy thừa là bao nhiêu?
O(log i) cho mục tiêu ở vị trí i, nên tối đa O(log n) với danh sách n giá trị. Nó cần O(1) bộ nhớ phụ và một danh sách đã sắp xếp.
Tìm kiếm lũy thừa khác tìm kiếm nhị phân thế nào?
Tìm kiếm nhị phân bắt đầu với toàn bộ danh sách và cần biết độ dài của nó. Tìm kiếm lũy thừa trước tiên gấp đôi để tìm một đoạn chứa mục tiêu, rồi chỉ tìm kiếm nhị phân trên đoạn đó. Nó nhanh hơn khi mục tiêu gần đầu và hoạt động mà không cần biết độ dài.
Vì sao gấp đôi bước nhảy mà không cộng một lượng cố định?
Cộng một bước cố định là tìm kiếm nhảy bước, cần khoảng n chia cho bước lần xem để đi hết danh sách. Gấp đôi thì đến vị trí i trong khoảng log₂ i lần xem, và đoạn nó để lại không bao giờ lớn hơn gấp đôi mức cần thiết, nên tìm kiếm nhị phân sau đó vẫn ngắn.
Tìm kiếm lũy thừa được dùng ở đâu?
Trong tìm kiếm dữ liệu đã sắp xếp không giới hạn hoặc rất dài, trong trộn các dãy con đã sắp xếp (galloping trong Timsort), và trong tìm vị trí đầu tiên mà một điều kiện trở thành đúng khi không biết giới hạn trên.
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.
Thử tìm kiếm lũy thừa