Thuật toán tìm kiếm tuyến tính (Linear Search)

1. Phát biểu bài toán tìm kiếm

Cho trước một danh sách gồm n phần tử. Bài toán tìm kiếm là bài toán tìm phần tử x có giá trị cho trước trong danh sách. Nếu phần tử đó tồn tại trong danh sách thì xuất vị trí của nó trong danh sách. Nếu phần tử đó không tồn tại trong danh sách thì xuất thông báo không tìm thấy.

Chúng ta có thể phát biểu bài toán như sau:

– Đầu vào (input):

• • Một danh sách gồm n phần tử a_0,a₁,a₂,…,a_n-1. Thường dùng mảng một chiều để lưu danh sách này.
  • Phần tử cần tìm là x.

– Đầu ra (output): Nếu tìm được phần tử x ở vị trí thứ k trong danh sách thì xuất kết quả là k, ngược lại nếu không tìm thấy thì xuất kết quả là –1.

Có 2 thuật toán tìm kiếm thường được sử dụng là:

• • Thuật toán tìm kiếm tuyến tính (Linear Search)
  • Thuật toán tìm kiếm nhị phân (Binary Search)

2. Thuật toán tìm kiếm tuyến tính

Còn gọi là tìm kiếm tuần tự. Ý tưởng của thuật toán này như sau:

So sánh x lần lượt với phần tử thứ 1, thứ 2,…của danh sách cho đến khi gặp được phần tử cần tìm. Nếu tìm hết mảng mà không thấy thì xuất thông báo không tìm thấy.

Các bước của thuật toán:

Bước 1: Gán i = 0; //bắt đầu từ phần tử đầu tiên của mảng

Bước 2: So sánh a[i] với x, 2 khả năng có thể xảy ra:

            + a[i] == x: Tìm thấy -> Xuất kết quả là i -> Dừng.

            + a[i] !=x: Chuyển qua Bước 3.

Bước 3: i = i + 1; //xét tiếp phần tử kế tiếp 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.

Minh họa thuật toán tìm kiếm tuyến tính

Tìm phần tử x=1 trong mảng bên dưới.

Lần lượt so sánh x với các phần tử trong mảng.

Tìm được x trong mảng.

Cài đặt thuật toán tìm kiếm tuyến tính với C++

Hàm LinearSearch() trả về i là vị trí của x trong mảng nếu tìm thấy x, ngược lại trả về -1.

int LinearSearch(int a[], int n, int x)
{
	int i=0;
	while((i<n)&&(a[i]!=x)){
		i++;
	}
	if(i==n){
		return -1;//Tìm không thấy x
	}
	else{
		return i;//Tìm thấy x
	}
}

Nhận xét:

Thuật toán tìm kiếm tuyến tính sử dụng 2 phép so sánh là i<n và a[i]!=x. Trường hợp xấu nhất, mỗi phép so sánh này đều có thể thực hiện n lần. Do đó, số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n. Độ phức tạp của thuật toán là O(n).

Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán, ta thêm phần tử “lính canh” vào cuối danh sách. Cùng xem cải thiết của thuật toán bên dưới.

3. Cải tiến thuật toán tìm kiếm tuyến tính

Cài đặt thuật toán tìm kiếm tuyến tính cải tiến với C++

int LinearSearch(int a[], int n, int x){
	int i=0; a[n]=x; //a[n] là phần tử “lính canh”
	while(a[i]!=x){
		i++;
	}
	if(i==n){
		return -1; //Tìm không thấy x
	}
	else{
		return i; //Tìm thấy x
	}
}

Ý tưởng:

Gán phần tử a[n]=x, mảng a có thêm phần tử cuối cùng là x. Do đó, khi tìm x trong mảng a thì chắc chắn sẽ tìm thấy. Nhưng nếu tìm thấy x ở vị trí cuối cùng n thì coi như không tìm thấy x. Nếu tìm thấy x ở vị trí khác n (từ 0 đến n-1) thì có nghĩa là tìm thấy x.

Nhận xét:

Thuật toán tìm kiếm tuyến tính cải tiến chỉ sử dụng 1 phép so sánh a[i]!=x. Trường hợp xấu nhất, số phép so sánh của thuật toán là n. Tức là giảm được phân nữa phép so sánh của thuật toán tìm kiếm thông thường.