NỘI DUNG
Thuật toán tìm kiếm tuần tự (Sequential Search Algorithm) là một phương pháp tìm kiếm giá trị trong một danh sách, mảng, hoặc chuỗi một cách tuần tự, tức là từ phần tử đầu tiên đến phần tử cuối cùng của danh sách. Nó là phương pháp tìm kiếm đơn giản nhất và cơ bản nhất, phù hợp để sử dụng cho các danh sách nhỏ hoặc không được sắp xếp.
Các bước thực hiện thuật toán tìm kiếm tuần tự
Thuật toán tìm kiếm tuần tự thực hiện như sau:
Bước 1. Bắt đầu từ phần tử đầu tiên của danh sách.
Bước 2. Kiểm tra xem phần tử đó có bằng giá trị tìm kiếm hay không. Nếu có, trả về vị trí của phần tử đó trong danh sách.
Bước 3. Nếu phần tử hiện tại không bằng giá trị tìm kiếm, di chuyển đến phần tử tiếp theo trong danh sách và tiếp tục kiểm tra cho đến khi tìm thấy giá trị tìm kiếm hoặc đã kiểm tra hết tất cả các phần tử trong danh sách.
Bước 4. Nếu tìm thấy giá trị tìm kiếm, trả về vị trí của phần tử đó trong danh sách. Nếu không tìm thấy, trả về giá trị không tìm thấy.
Ví dụ về thuật toán tìm kiếm tuần tự
Ví dụ: Tìm kiếm giá trị 7 trong mảng a = [1, 3, 5, 7, 9]
Bước 1: Khởi tạo biến i = 0, phần tử đầu tiên của mảng là a[0] = 1
Bước 2: Kiểm tra a[0] có bằng 7 không, không bằng
Bước 3: Di chuyển đến phần tử tiếp theo, i = 1, a[1] = 3
Bước 4: Kiểm tra a[1] có bằng 7 không, không bằng
Bước 5: Di chuyển đến phần tử tiếp theo, i = 2, a[2] = 5
Bước 6: Kiểm tra a[2] có bằng 7 không, không bằng
Bước 7: Di chuyển đến phần tử tiếp theo, i = 3, a[3] = 7
Bước 8: Kiểm tra a[3] có bằng 7 không, bằng, trả về giá trị 3 (vị trí của phần tử có giá trị bằng 7 trong mảng a)
Nếu giá trị tìm kiếm không có trong danh sách, thuật toán sẽ kiểm tra hết tất cả các giá trị.
Ví dụ: Tìm kiếm giá trị 4 trong mảng a = [1, 3, 5, 7, 9]
Bước 1: Khởi tạo biến i = 0, phần tử đầu tiên của mảng là a[0] = 1
Bước 2: Kiểm tra a[0] có bằng 4 không, không bằng
Bước 3: Di chuyển đến phần tử tiếp theo, i = 1, a[1] = 3
Bước 4: Kiểm tra a[1] có bằng 4 không, không bằng
Bước 5: Di chuyển đến phần tử tiếp theo, i = 2, a[2] = 5
Bước 6: Kiểm tra a[2] có bằng 4 không, không bằng
Bước 7: Di chuyển đến phần tử tiếp theo, i = 3, a[3] = 7
Bước 8: Kiểm tra a[3] có bằng 4 không, không bằng
Bước 9: Di chuyển đến phần tử tiếp theo, i = 4, a[4] = 9
Bước 10: Kiểm tra a[4] có bằng 4 không, không bằng
Bước 11: Kiểm tra hết tất cả các phần tử trong danh sách, không tìm thấy giá trị 4, trả về giá trị không tìm thấy
Cài đặt thuật toán tìm kiếm tuần tự với Python
def sequential_search(arr, x):
# Duyệt qua từng phần tử của mảng
for i in range(len(arr)):
# Kiểm tra nếu phần tử có giá trị bằng x
if arr[i] == x:
return i # Trả về chỉ số của phần tử được tìm thấy
# Nếu không tìm thấy, trả về -1
return -1
# Ví dụ
arr = [1, 3, 5, 7, 9]
x = 5
result = sequential_search(arr, x)
if result != -1:
print("Phần tử", x, "được tìm thấy tại vị trí", result)
else:
print("Không tìm thấy phần tử", x, "trong mảng")
Cài đặt thuật toán tìm kiếm tuần tự với C++
#include <iostream>
using namespace std;
int sequentialSearch(int arr[], int n, int x) {
// Duyệt qua từng phần tử của mảng
for (int i = 0; i < n; i++) {
// Kiểm tra nếu phần tử có giá trị bằng x
if (arr[i] == x) {
return i; // Trả về chỉ số của phần tử được tìm thấy
}
}
// Nếu không tìm thấy, trả về -1
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int x = 5;
int result = sequentialSearch(arr, 5, x);
if (result != -1) {
cout << "Phan tu " << x << " duoc tim thay tai vi tri " << result << endl;
} else {
cout << "Khong tim thay phan tu " << x << " trong mang" << endl;
}
return 0;
}
Sự khác biệt giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm tuyến tính
Thuật toán tìm kiếm tuần tự là một thuật toán tìm kiếm giá trị trong một danh sách một cách tuần tự. Nó duyệt qua từng phần tử của danh sách để tìm kiếm giá trị cần tìm. Thuật toán này là phương pháp tìm kiếm đơn giản nhất và cơ bản nhất, phù hợp để sử dụng cho các danh sách nhỏ hoặc không được sắp xếp. Tuy nhiên, vì độ phức tạp của thuật toán là O(n), nghĩa là nó có thể mất đến O(n) lần lặp để tìm thấy giá trị cần tìm (trong trường hợp giá trị đó nằm ở cuối danh sách), nên nó không phù hợp để sử dụng cho các danh sách lớn hoặc khi ta cần tìm kiếm nhanh hơn.
Trong khi đó, thuật toán tìm kiếm tuyến tính là một thuật toán tìm kiếm giá trị trong một danh sách một cách tuyến tính. Nó cũng duyệt qua từng phần tử của danh sách, nhưng nếu phần tử hiện tại khác với giá trị cần tìm thì nó sẽ tiếp tục duyệt đến phần tử tiếp theo, trong khi thuật toán tìm kiếm tuần tự kiểm tra tất cả các phần tử trong danh sách. Tuy cũng có độ phức tạp là O(n), nhưng thuật toán tìm kiếm tuyến tính thường có hiệu suất tốt hơn khi tìm kiếm các giá trị ở phần đầu của danh sách, vì nó sẽ dừng tìm kiếm ngay khi tìm thấy giá trị cần tìm.
Tóm lại, cả hai thuật toán đều có ưu điểm và hạn chế riêng. Tùy vào trường hợp cụ thể mà ta có thể chọn thuật toán phù hợp để tối ưu hiệu suất tìm kiếm.