Kỹ thuật Đặt Lính Canh trong PHP (Sentinel Linear Search)

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:

1. 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.
2. Duyệt mảng từ đầu cho đến khi tìm thấy phần tử cần tìm.
3. 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:

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";
}

Giải thích chi tiết:

• Hàm sentinelLinearSearch(&$array, $target):
  • Hàm nhận vào một mảng và giá trị cần tìm.
  • Biến $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.
  • Phần tử cuối cùng của mảng được thay thế bằng phần tử cần tìm ($target), tạo ra một “lính canh”.
  • Vòng lặp while tiếp tục cho đến khi tìm thấy phần tử cần tìm.
  • Sau khi kết thúc tìm kiếm, phần tử cuối cùng được khôi phục và kiểm tra xem chỉ số tìm được có nằm trong phạm vi của mảng ban đầu hay không.

Kết quả:

Nếu $target = 90, kết quả sẽ là:

Phần tử 90 được tìm thấy tại vị trí: 3

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.

• PHP