Thuật toán sắp xếp : LINEAR SEARCH

Ý 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 1i = 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 3i = i + 1;     // xét tiếp phần tử kế trong mảng

                Nếu iN : 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ưởng

Đặ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.

 

Giải thuật

            Bước 1i = 1;

                            a[N+1] = x;            // phần tử “lính canh”

            Bước 2:  So sánh a[i] với x.

                            +   Nếu a[i] = x: Sang Bước 3

                            +   Nếu a[i] ≠ xi = i + 1;   Lặp lại bước 2.

            Bước 3:  Nếu iN : tìm thấy x tại vị trí i.

                Ngược lại: không tìm thấy x trong mảng.

 

 

Chủ đề liên quan
Thuật toán sắp xếp : LINEAR SEARCH

Cùng chuyên mục

Xem nhiều hôm nay