Tìm kiếm tuyến tính
Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm


Bài hoặc đoạn này cần được wiki hóa theo các quy cách định dạng và văn phong Wikipedia. Xin hãy giúp phát triển bài này bằng cách liên kết trong đến các mục từ thích hợp khác.

Tìm kiếm tuyến tính` là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. Thuật toán tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. Các bước tiến hành như sau :
•Bước 1:
i = 1; // bắt đầu từ phần tử đầu tiên của dãy
•Bước 2: So sánh a[i] với x, có 2 khả năng : a[i] = x : Tìm thấy. Dừng a[i] != x : Sang Bước 3.
•Bước 3 :
i = i+1; // xét tiếp phần tử kế trong mảng

Nếu i >N: Hết mảng,không tìm thấy.Dừng
Ngược lại: Lặp lại Bước 2.

Cài đặt
Từ mô tả trên đây của thuật toán tìm tuyến tính , có thể cài đặt hàm LinearSearch để xác định vị trí của phần tử có khoá x trong mảng a :
int LinearSearch(int a[], int N, int x) {
int i=0;
while ((iif(i==N) return -1; // tìm hết mảng nhưng không có x
else return i; // a[i] là phần tử có khoá x
}
Trong cài đặt trên đây, nhận thấy mỗi lần lặp của vòng lặp while phải tiến thành kiểm tra 2 điều kiện (iint LinearSearch(int a[],int N,int x) {
int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]
a[N] = x; // thêm phần tử thứ N+1
while (a[i]!=x ) i++;
if (i==N)
return -1; // tìm hết mảng nhưng không có x
else return i; // tìm thấy x tại vị trí i
}
Ðánh giá giải thuật Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Trường hợp giải thuật tìm tuyến tính, có: Trường hợp Số lần so sánh Giải thích Tốt nhất 1 Phần tử đầu tiên có giá trị x Xấu nhất n+1 Phần tử cuối cùng có giá trị x Trung bình (n+1)/2 Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau. Vậy giải thuật tìm tuyến tính Giải thuật tìm tuyến tính(có độ phức tạp tính toán cấp n: T(n) = O(n) không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương Một thuật(pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ. toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.