Tổng quan
Exponential Search (tìm kiếm mũ) tìm mục tiêu trong mảng đã sắp xếp bằng cách trước tiên xác định một khoảng chắc chắn chứa nó, rồi chạy Binary Search bên trong khoảng đó. Nó bắt đầu tại chỉ số 1 và liên tục nhân đôi biên cho đến khi vượt qua mục tiêu.
Giai đoạn nhân đôi này nhanh chóng khoanh vùng mục tiêu ở gần đầu mảng, khiến Exponential Search đặc biệt hấp dẫn với dữ liệu đã sắp xếp không giới hạn hoặc rất lớn, khi mục tiêu thường nằm gần phần đầu.
Tìm kiếm lũy thừa hoạt động thế nào?
- Kiểm tra chỉ số 0 trước; nếu nó chứa mục tiêu, trả về ngay.
- Bắt đầu với biên bằng 1 và nhân đôi nó (1, 2, 4, 8, …) trong khi phần tử tại biên vẫn nhỏ hơn mục tiêu.
- Dừng khi giá trị tại biên bằng hoặc vượt mục tiêu, hoặc biên đã ra khỏi mảng.
- Điều này cho một khoảng giữa biên trước và biên hiện tại chắc chắn chứa mục tiêu.
- Chạy Binary Search trong khoảng đã khoanh đó để tìm chỉ số chính xác.
Khi nào nên dùng?
- Dữ liệu đã sắp xếp không giới hạn hoặc dạng luồng mà độ dài chưa biết trước.
- Mảng lớn đã sắp xếp khi mục tiêu được kỳ vọng nằm gần phần đầu.
- Làm phần đầu khoanh vùng, giao một khoảng nhỏ đã biết cho Binary Search.
Phân tích độ phức tạp
Nếu mục tiêu nằm ở chỉ số i, giai đoạn nhân đôi tốn O(log i) bước để khoanh vùng, và Binary Search tiếp theo trên khoảng đó cũng O(log i), cho tổng thời gian O(log n) ở trường hợp xấu nhất. Nó cần mảng đã sắp xếp và dùng O(1) bộ nhớ phụ khi cài đặt lặp.
Câu hỏi thường gặp
Vì sao dùng Exponential Search thay vì Binary Search thuần?
Nó tỏa sáng khi độ dài mảng chưa biết hoặc gần như không giới hạn: giai đoạn nhân đôi khám phá một khoảng hợp lệ mà không cần biết trước tổng kích thước, rồi giao lại cho Binary Search.
Exponential Search có nhanh hơn Binary Search không?
Cả hai đều O(log n), nhưng Exponential Search có thể nhanh hơn khi mục tiêu nằm gần đầu, vì nó tìm ra khoảng khoanh vùng chặt trong O(log i) bước tỉ lệ với vị trí của mục tiêu.