*Ý tưởng
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.
*Giải thuật
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
Cách 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 hết mảng nhưng không có x
else
return i;// a[i] là phần tử có khoá x
}
Cách 2:Cải tiến (dùng lính canh) giúp giảm bớt một phép so sánh(tối ưu hơn cách 1)
int LinearSearch2(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
}
Lưu ý: Kết quả trả về của 2 hàm này là vị trí tìm thấy của x trong mảng. Nếu kết quả trả về là -1 là mảng không có phần tử x