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.
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:
function sentinelLinearSearch(&$array, $target) {
// Lưu lại phần tử cuối cùng để khôi phục sau khi tìm kiếm
$last = $array[count($array) - 1];
// Đặt lính canh bằng cách gán phần tử cần tìm vào vị trí cuối cùng
$array[count($array) - 1] = $target;
// Bắt đầu tìm kiếm từ đầu mảng
$i = 0;
while ($array[$i] != $target) {
$i++;
}
// Khôi phục phần tử cuối cùng của mảng
$array[count($array) - 1] = $last;
// Kiểm tra xem phần tử tìm thấy có nằm trong mảng ban đầu hay là lính canh
if ($i < count($array) - 1 || $array[count($array) - 1] == $target) {
return $i;
} else {
return -1; // Nếu lính canh bị trùng với phần tử cần tìm, vẫn trả về vị trí hợp lệ
}
}
// Ví dụ sử dụng
$array = [34, 78, 12, 90, 56, 23];
$target = 90;
$result = sentinelLinearSearch($array, $target);
if ($result != -1) {
echo "Phần tử $target được tìm thấy tại vị trí: $result";
} else {
echo "Phần tử $target không có trong mảng";
}
sentinelLinearSearch(&$array, $target):
$last được sử dụng để lưu phần tử cuối cùng của mảng, giúp khôi phục mảng về trạng thái ban đầu sau khi tìm kiếm.$target), tạo ra một “lính canh”.while tiếp tục cho đến khi tìm thấy phần tử cần tìm.Nếu $target = 90, kết quả sẽ là:
Phần tử 90 được tìm thấy tại vị trí: 3
Nếu $target = 100 không có trong mảng:
Phần tử 100 không có trong mảng
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.
