Ý tưởng
Cho mảng a gồm N phần tử, cần tìm x trong mảng a.
So sánh x lần lượt với phần tử thứ 1, thứ 2,…của mảng a cho đến khi gặp 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.
+ Nếu a[i] = x: Tìm thấy. Dừng.
+ Nếu 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 : lặp lại Bước 2.
Ngược lại: Hết mảng. Không tìm thấy. Dừng
LINEAR SEARCH
(có lính canh)
Đặt một phần tử có giá trị x vào cuối mảng, gọi đây là phần tử “lính canh”. Như vậy, ta bảo đảm luôn tìm thấy x trong mảng, và dựa vào vị trí tìm thấy để đưa ra kết luận.
Phương pháp cải tiến này giúp giảm bớt một phép so sánh trong vòng lặp.
Bước 1: i = 1;
a[N+1] = x; // phần tử “lính canh”
+ Nếu a[i] = x: Sang Bước 3
+ Nếu a[i] ≠ x: i = i + 1; Lặp lại bước 2.
Bước 3: Nếu i ≤ N : tìm thấy x tại vị trí i.
Ngược lại: không tìm thấy x trong mảng.