Tìm kiếm tuyến tính là gì? Tìm kiếm tuyến tính trong PHP

1. Tìm kiếm tuyến tính là gì?

Tìm kiếm tuyến tính (hay Linear Search) là một thuật toán tìm kiếm đơn giản nhất, trong đó một phần tử trong một danh sách được kiểm tra lần lượt từ đầu đến cuối cho đến khi tìm thấy phần tử cần tìm hoặc đã kiểm tra hết danh sách.

Trong tìm kiếm tuyến tính, mỗi phần tử trong danh sách được so sánh với phần tử cần tìm một cách tuần tự, từ phần tử đầu tiên cho đến phần tử cuối cùng. Nếu tìm thấy phần tử cần tìm, thuật toán trả về vị trí của phần tử đó. Nếu không, thuật toán trả về kết quả cho biết rằng phần tử không tồn tại trong danh sách.

Ưu điểm:

• Đơn giản: Tìm kiếm tuyến tính rất dễ hiểu và dễ cài đặt.
• Linh hoạt: Có thể áp dụng trên mọi loại dữ liệu, bao gồm cả danh sách không có thứ tự.
• Không yêu cầu sắp xếp: Thuật toán này không yêu cầu danh sách phải được sắp xếp trước.

Nhược điểm:

• Hiệu suất kém: Hiệu suất của tìm kiếm tuyến tính chậm khi danh sách có số lượng phần tử lớn, vì mỗi phần tử đều phải được kiểm tra.
• Thời gian thực thi phụ thuộc vào kích thước danh sách: Độ phức tạp của thuật toán là O(n) (n là số lượng phần tử trong danh sách), tức là thời gian thực hiện tăng tuyến tính theo số lượng phần tử trong danh sách.

Các bước của thuật toán tìm kiếm tuyến tính:

1. Bắt đầu từ phần tử đầu tiên của danh sách.
2. So sánh phần tử hiện tại với giá trị cần tìm.
3. Nếu giá trị phần tử hiện tại bằng với giá trị cần tìm, trả về vị trí của phần tử đó.
4. Nếu không bằng, di chuyển đến phần tử tiếp theo và lặp lại bước 2.
5. Nếu duyệt hết danh sách mà không tìm thấy giá trị cần tìm, trả về kết quả là phần tử không tồn tại trong danh sách.

2. Ví dụ tìm kiếm tuyến tính trong PHP

Đề bài:

Cho một mảng chứa các số nguyên, hãy viết một hàm tìm kiếm tuyến tính để tìm xem một giá trị có tồn tại trong mảng hay không. Nếu tồn tại, trả về vị trí của phần tử đó, nếu không tồn tại, trả về một thông báo rằng giá trị không có trong mảng.

Cài đặt:

Dưới đây là ví dụ minh họa cách cài đặt thuật toán tìm kiếm tuyến tính trong PHP:

function linearSearch($array, $target) {
    // Duyệt qua từng phần tử trong mảng
    for ($i = 0; $i < count($array); $i++) {
        // So sánh phần tử hiện tại với giá trị cần tìm
        if ($array[$i] == $target) {
            // Trả về vị trí của phần tử tìm thấy
            return $i;
        }
    }
    // Nếu duyệt hết mảng mà không tìm thấy, trả về -1
    return -1;
}

// Ví dụ sử dụng
$array = [34, 78, 12, 90, 56, 23];
$target = 90;

$result = linearSearch($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 linearSearch($array, $target):
  • Nhận vào hai tham số: mảng $array cần tìm kiếm và giá trị cần tìm $target.
  • Sử dụng vòng lặp for để duyệt qua từng phần tử trong mảng.
  • Ở mỗi bước lặp, so sánh giá trị của phần tử hiện tại $array[$i] với giá trị cần tìm $target. Nếu tìm thấy, trả về vị trí (chỉ số) của phần tử đó.
  • Nếu đã duyệt hết mảng mà không tìm thấy giá trị cần tìm, trả về -1 để biểu thị rằng giá trị không tồn tại trong mảng.
• Ví dụ sử dụng:
  • Mảng $array = [34, 78, 12, 90, 56, 23] chứa các số nguyên.
  • Giá trị cần tìm là $target = 90.
  • Sau khi chạy thuật toán, tìm thấy giá trị 90 ở vị trí thứ 3 trong mảng (chỉ số 3 vì PHP đánh số mảng từ 0).

Kết quả:

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 thay đổi giá trị cần tìm thành một số không tồn tại trong mảng, ví dụ $target = 100, kết quả sẽ là:

Phần tử 100 không có trong mảng

3. Một số trường hợp ví dụ khác:

a. Tìm kiếm phần tử có trong mảng:

$array = [10, 20, 30, 40, 50];
$target = 30;

$result = linearSearch($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";
}

Kết quả:

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

b. Tìm kiếm phần tử không có trong mảng:

$array = [10, 20, 30, 40, 50];
$target = 60;

$result = linearSearch($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";
}

Kết quả:

Phần tử 60 không có trong mảng

Tóm tắt:

• Tìm kiếm tuyến tính là thuật toán kiểm tra tuần tự từng phần tử của một danh sách để tìm một phần tử cụ thể.
• Đây là một thuật toán đơn giản nhưng không hiệu quả khi danh sách có số lượng lớn phần tử, với độ phức tạp thời gian O(n).
• Thuật toán này dễ hiểu, dễ cài đặt và không yêu cầu mảng phải sắp xếp.

• PHP