Thuật toán tìm kiếm tuyến tính (Linear Search Algorithm) là một thuật toán tìm kiếm đơn giản nhất trong các thuật toán tìm kiếm. Thuật toán này được sử dụng để tìm kiếm một phần tử cụ thể trong một danh sách đã cho bằng cách kiểm tra từng phần tử của danh sách theo thứ tự từ đầu đến cuối cho đến khi tìm thấy phần tử cần tìm hoặc đến cuối danh sách.
Các bước thực hiện thuật toán tìm kiếm tuyến tính
Thuật toán tìm kiếm tuyến tính hoạt động như sau:
- Bước 1: Khởi tạo biến i bằng 0.
- Bước 2: Kiểm tra phần tử thứ i của danh sách nếu phần tử này trùng với giá trị cần tìm, trả về vị trí của phần tử này.
- Bước 3: Tăng giá trị của i lên 1 và quay lại bước 2 cho đến khi tìm thấy phần tử cần tìm hoặc đã kiểm tra hết danh sách.
Nếu tìm kiếm đến cuối danh sách mà không tìm thấy phần tử cần tìm, thuật toán trả về kết quả không tìm thấy.
Cài đặt thuật toán tìm kiếm tuyến tính với Python
def linear_search(arr, x):
"""
Tìm kiếm giá trị x trong danh sách arr bằng thuật toán tìm kiếm tuyến tính
Trả về vị trí đầu tiên của x trong danh sách nếu tìm thấy, hoặc -1 nếu không tìm thấy
"""
n = len(arr)
for i in range(n):
if arr[i] == x:
return i
return -1
arr = [1, 3, 5, 7, 9]
x = 5
result = linear_search(arr, x)
if result != -1:
print(f"Tìm thấy giá trị {x} tại vị trí {result}")
else:
print(f"Không tìm thấy giá trị {x}")
Cài đặt thuật toán tìm kiếm tuyến tính với C++
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int x) {
for(int i=0; i<n; i++) {
if(arr[i] == x) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 8;
int result = linearSearch(arr, n, x);
if(result != -1) {
cout << "Tìm thấy giá trị " << x << " tại vị trí " << result << endl;
} else {
cout << "Không tìm thấy giá trị " << x << endl;
}
return 0;
}
Tổng kết
Thuật toán tìm kiếm tuyến tính là thuật toán đơn giản và dễ hiểu, được sử dụng để tìm kiếm một giá trị cụ thể trong một danh sách. Thuật toán tìm kiếm tuyến tính được gọi là “tuyến tính” vì nó duyệt danh sách theo từng phần tử một cho đến khi tìm thấy giá trị cần tìm hoặc duyệt hết toàn bộ danh sách.
Tuy nhiên, một nhược điểm của thuật toán tìm kiếm tuyến tính là thời gian chạy của nó phụ thuộc vào kích thước của danh sách. Khi danh sách lớn, thuật toán sẽ phải duyệt qua toàn bộ danh sách, dẫn đến thời gian chạy dài và không hiệu quả.
Để giải quyết vấn đề này, có thể sử dụng các thuật toán tìm kiếm khác như thuật toán tìm kiếm nhị phân để tìm kiếm trong danh sách đã được sắp xếp một cách hiệu quả hơn.
Tóm lại, thuật toán tìm kiếm tuyến tính là một trong những thuật toán tìm kiếm cơ bản và cần thiết trong lập trình, tuy nhiên, cần cân nhắc đến kích thước của danh sách để đánh giá hiệu quả của thuật toán.