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:

linearSearch($array, $target)

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