Kỹ thuật đặt lính canh (Sentinel technique) là một cải tiến của thuật toán tìm kiếm tuyến tính nhằm tối ưu hóa hiệu suất bằng cách giảm số lần kiểm tra điều kiện trong vòng lặp. Thay vì kiểm tra hai điều kiện trong mỗi bước lặp (một để kiểm tra xem phần tử có phải là phần tử cần tìm và một để kiểm tra xem có vượt quá giới hạn của mảng hay không), kỹ thuật lính canh chỉ kiểm tra một điều kiện duy nhất.
Ý tưởng cơ bản:
- Ta sẽ thêm một phần tử đặc biệt vào cuối mảng (được gọi là lính canh) để đảm bảo rằng phần tử cần tìm sẽ luôn xuất hiện trong mảng, giúp loại bỏ việc kiểm tra giới hạn mảng ở mỗi bước lặp.
- Sau khi tìm thấy phần tử, nếu phần tử đó là lính canh thì điều đó có nghĩa là giá trị cần tìm không có trong mảng.
Các bước thực hiện kỹ thuật đặt lính canh:
- Thêm phần tử cần tìm (hoặc một giá trị đặc biệt) vào cuối mảng dưới dạng lính canh.
- Duyệt mảng từ đầu cho đến khi tìm thấy phần tử cần tìm.
- Nếu phần tử tìm thấy ở ngoài phạm vi mảng ban đầu (tức là lính canh), điều này có nghĩa là phần tử cần tìm không có trong mảng.
Ví dụ cài đặt kỹ thuật đặt lính canh trong PHP:
Giả sử chúng ta có một mảng và muốn tìm một giá trị cụ thể trong mảng bằng kỹ thuật đặt lính canh:
sentinelLinearSearch(&$array, $target)
Trường hợp phần tử không có trong mảng:
Nếu $target = 100 không có trong mảng:
Phần tử 100 không có trong mảng
Tóm tắt kỹ thuật lính canh:
- Mục tiêu: Giảm số lần kiểm tra điều kiện trong vòng lặp, tăng hiệu suất của tìm kiếm tuyến tính.
- Phương pháp: Thêm phần tử đặc biệt (lính canh) vào cuối mảng để đảm bảo phần tử cần tìm luôn có trong mảng, loại bỏ việc kiểm tra giới hạn mảng ở mỗi vòng lặp.
- Lợi ích: Giảm chi phí tính toán vì chỉ cần kiểm tra một điều kiện duy nhất trong vòng lặp.
- Nhược điểm: Cần lưu trữ và khôi phục lại phần tử cuối cùng của mảng sau khi tìm kiếm.
Kỹ thuật đặt lính canh đặc biệt hữu ích trong các bài toán mà hiệu suất tìm kiếm cần được tối ưu hóa, đặc biệt là trong các ứng dụng yêu cầu tìm kiếm nhiều lần trên một tập dữ liệu lớn.
