Tổng quan
Ternary Search chia khoảng thành ba phần thay vì hai. Mỗi vòng đặt hai điểm dò bên trong khoảng, so sánh chúng, rồi loại bỏ một phần ba không thể chứa đáp án.
Trên mảng đã sắp, nó là một thứ thú vị chứ không phải cải tiến: mỗi vòng loại được một phần ba khoảng nhưng phải trả hai phép so sánh, trong khi binary search loại một nửa chỉ với một phép. Đất diễn thật sự của nó là bài toán tối ưu — tìm đỉnh của một hàm đơn điệu-một-đỉnh, nơi bạn không thể hỏi 'mục tiêu lớn hơn hay nhỏ hơn' vì không có mục tiêu nào cả, chỉ có một hình dạng.
Ternary Search hoạt động thế nào?
- Lấy khoảng hiện tại [lo, hi] và tính hai điểm chia: m1 ở một phần ba, m2 ở hai phần ba.
- So sánh mục tiêu với giá trị tại m1. Nếu khớp thì dừng; nếu nhỏ hơn thì đáp án nằm trong [lo, m1 − 1].
- Nếu không, so sánh với giá trị tại m2. Nếu khớp thì dừng; nếu lớn hơn thì đáp án nằm trong [m2 + 1, hi].
- Nếu nó nằm giữa hai điểm dò, đáp án nằm ở một phần ba giữa [m1 + 1, m2 − 1].
- Lặp lại trên phần ba còn sống cho tới khi khớp hoặc khoảng rỗng.
Khi nào nên dùng?
- Tìm cực đại hoặc cực tiểu của một hàm đơn điệu-một-đỉnh — trường hợp nó thật sự hơn các phương án khác.
- Các bài tối ưu trong lập trình thi đấu khi không gian tìm kiếm liên tục và hàm mục tiêu có một đỉnh duy nhất.
- Dạy ý tưởng chia để trị: nó cho thấy rõ tỉ lệ chia là một lựa chọn điều chỉnh được, không phải quy luật.
- Không phải công cụ để tra cứu thường trên mảng đã sắp — binary search làm cùng việc với ít phép so sánh hơn.
Phân tích độ phức tạp
Mỗi vòng thu khoảng còn một phần ba, nên số vòng là log₃ n — ít hơn log₂ n của binary search. Nhưng mỗi vòng tốn tới hai phép so sánh thay vì một, và 2·log₃ n xấp xỉ 1,26·log₂ n. Vậy nên nó làm nhiều việc so sánh hơn hẳn dù chạy ít vòng hơn, và đó là lý do binary search vẫn là lựa chọn mặc định. Bộ nhớ là O(1) nếu cài lặp.
Câu hỏi thường gặp
Nếu nó chạy ít vòng hơn, sao lại chậm hơn?
Vì chi phí không nằm ở số vòng mà ở số phép so sánh. Ternary search mua được ít vòng hơn bằng cách chi hai phép so sánh mỗi vòng, và phép tính cho ra kết quả bất lợi: khoảng 1,26 lần số so sánh của binary search trên cùng một mảng.
Hàm đơn điệu-một-đỉnh là gì, và vì sao nó quan trọng ở đây?
Là hàm tăng lên tới một đỉnh duy nhất rồi giảm (hoặc ngược lại). Chính hình dạng đó cho phép hai điểm dò quyết định đỉnh nằm phía nào: nếu f(m1) < f(m2) thì đỉnh không thể nằm bên trái m1. Với hai đỉnh, suy luận đó đổ vỡ và phép tìm có thể loại nhầm vùng chứa đáp án.
Có thể chia thành bốn phần, hay mười phần không?
Được, và càng chia càng tệ. Tìm kiếm k-phân cần k − 1 phép so sánh để loại bỏ tỉ lệ (k−1)/k, và tỉ lệ đó xấu đi khi k tăng. Hai là tối ưu cho tìm kiếm dựa trên so sánh, đó là lý do sâu xa khiến binary search có mặt khắp nơi.