Thuật toán tìm kiếm tuần tự

Đăng bởi Admin

Tháng 10 6, 2022

Trong thực tế, có rất nhiều bài toán, nhưng hầu như tất cả chúng đều quy về một bài toán duy nhất, đó chính là bài toán tìm kiếm. Từ những nhu cầu thực tế đó, bài toán tìm kiếm dẫn đến chúng ta phải tạo ra thuật toán tìm kiếm để giải quyết nó. Vậy thì thuật toán tìm kiếm là gì? Thuật toán tìm kiếm (searching algorithm) là thuật toán giúp ta tìm ra trong một tập dữ liệu đã cho một hoặc nhiều phần tử thỏa mãn yêu cầu tìm kiếm.

Tùy theo cấu trúc dữ liệu mà chúng ta sẽ có những thuật toán tìm kiếm khác nhau phù hợp cho mỗi cấu trúc. Do đó, chúng ta không nên học thuộc lòng thuật toán tìm kiếm trên một tập dữ liệu, một cấu trúc dữ liệu trong một ngôn ngữ cụ thể nào đó. Hãy học ý tưởng của thuật toán và áp dụng nó linh hoạt cho các cấu trúc dữ liệu khác nhau trong các ngôn ngữ lập trình khác nhau.

Tìm kiếm tuần tự

Tìm kiếm tuần tự (sequential search) là thuật toán tìm kiếm bằng cách duyệt qua tất cả các phần tử của danh sách cho đến khi gặp phần tử cần tìm hoặc là đã hết danh sách. Do cách tìm kiếm duyệt từ đầu đến cuối này, độ phức tạp thời gian của thuật toán này sẽ là O(n).

Chúng ta có một mảng A có n phần tử bắt đầu từ vị trí 0. Để tìm kiếm phần tử x trong mảng A này, ta làm như sau:

Gán i = 0.
So sánh giá trị của A[i] và x:
- Nếu A[i] == x thì dừng và trả về giá trị của i (vị trí của x trong mảng A).
- Nếu A[i] != x thì sang bước 3.
Gán i = i + 1:
- Nếu i == n (tức hết mảng) thì dừng lại và trả kết quả là -1 (không tìm thấy x).
- Nếu i < n thì quay lại bước 2.

Mô phỏng C++

int Search(int A[],int n, int x)
{
    for(int i=0;i<n;i++)
        if(A[i]==x)
            return i;
    return -1;
}

Đánh giá: Mặc dù giải thuật Tìm kiếm tuần tự rất đơn giản và dễ cài đặt, tuy nhiên nhược điểm của nó nằm ở độ phức tạp. Trong trường hợp tốt nhất, giải thuật có độ phức tạp là O(1), nhưng trong trường hợp xấu nhất lên tới O(n). Vì vậy độ phức tạp tổng quát của giải thuật là O(n), chỉ phù hợp với những bài toán có kích thước không gian tìm kiếm nhỏ.

Ví dụ:

Cho một mảng một chiều gồm $\mathrm{n}$ số nguyên $a_1, a_2, \ldots, a_n$ và số nguyên $\mathrm{k}$ . Kiểm tra số nguyên $\mathrm{k}$ có xuất hiện mảng đã cho hay không? Nếu có thì ghi ra vị trí xuất hiện của số nguyên $\mathrm{k}$ trong mảng đó, nếu xuất hiện nhiều lần thì ghi ra vị trí xuất hiện đầu tiên. Nếu không xuất hiện thì ghi ra $-1$ .

Thuật toán:

– Sử dụng biến id để lưu lại vị trí xuất hiện đầu tiên của số $\mathrm{k}$
– Lần lượt so sánh các phần tử $a[i]$ với số $\mathrm{k}$ , nếu $\mathrm{a}[\mathrm{i}]=\mathrm{k}$ thì gán $\mathrm{id}=\mathrm{i}$ , thuật toán kết thúc.
– Nếu kiểm tra hết các phần từ $a[1], a[2], \ldots a[n]$ mà không có phần tử nào bằng k thì ghi ra $-1$ .

Chương trình:

#include<bits/stdc++.h>
using namespace std;
int A[1000010],n,k;
int Search(int A[],int n, int k)
{
    int id = -1;
    for(int i=1; i<=n; i++)
        if(A[i]==k)
        {
            id=i;
            break;
        }
    return id;
}
int main()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        cin>>A[i];
    cout<<Search(A,n,k);
}

Chia sẻ: