Tìm kiếm tuyến tính [serial về các thuật toán cơ bản trong lập trình]

Tìm kiếm tuyến tính (linear search) còn có tên khác là tìm kiếm tuần tự (sequential search) là một kỹ thuật tìm kiếm rất cơ bản và dễ hiểu trong lập trình, đây là kỹ thuật mà có khi bạn đã áp dụng rồi khi thậm chí chưa đọc lý thuyết về nó.

Tìm kiếm tuyến tính thực hiện tìm kiếm bằng cách duyệt qua từng phần tử trong mảng, và so sánh nó với giá trị cần tìm kiếm. Vấn đề với tìm kiếm tuyến tính là nó không có hiệu suất tốt trong các mảng lớn (ví dụ khi so sánh với tìm kiếm nhị phân). Tìm kiếm tuyến tính chỉ hiệu quả trên các mảng nhỏ, hoặc mảng không được sắp xếp.

Ví dụ về đoạn mã PHP sử dụng kiểu tìm kiếm tuyến tính:

function linear_search($arr, $x)
{
    $n = count($arr);
    for($i = 0; $i < $n; $i++)
    {
        if($arr[$i] == $x)
            return $i;
    }
    return -1;
}

$arr = array(1,3,6,8,9);
$x = 8;
$result = linear_search($arr, $x);

if($result == -1)
    echo "$x không có trong mảng";
else
    echo "$x có trong mảng tại vị trí $result";

Ngoài cách dùng for, bạn có thể dùng hàm foreach trong PHP để duyệt từng phần tử.

Mặc dù có hiệu suất thấp, tìm kiếm tuyến tính vẫn không thể thiếu trong lập trình, vì có những mảng chúng ta không sắp xếp được, hay có sắp xếp được thì cũng không hiệu quả / phù hợp để sử dụng các biện pháp tìm kiếm khác.

Đối với các mảng lớn, tìm kiếm tuyến tính có thể áp dụng mẹo chia thành các mảng nhỏ hơn, và đôi khi rất hiệu quả. Ví dụ bạn có danh sách họ tên của 100 ngàn người, và đầu vào là một chuỗi họ tên của một người cụ thể cần tìm kiếm. Khi ấy thay vì sử dụng một mảng duy nhất bao gồm cả 100 ngàn phần tử rồi duyệt tìm, bạn có thể chia thành 29 mảng theo ký tự chữ cái đầu của tên.

Ví dụ tên tôi là Nguyễn Đức Anh, thì chỉ cần tìm trong mảng có vần A là được, khi ấy không gian tìm kiếm sẽ giảm đi rất nhiều. Tất nhiên sẽ phải mất công nghĩ ra thuật toán sắp xếp trước theo thứ tự ABC, nhưng nó không khó khăn gì, và về lâu dài việc này sẽ tiết kiệm hơn nhiều thao tác tìm kiếm trên cả không gian gồm 100 ngàn phần tử trong ví dụ trên.