/codegym.vn/ - 138
Khi thao tác với mảng, việc triển khai thuật toán tìm kiếm tuyến tính khá đơn giản, chỉ
cần bắt đầu một vòng lặp ở đầu danh sách và so sánh mỗi phần tử với dữ liệu bạn
đang tìm kiếm. Nếu tìm thấy một phần tử phù hợp, quá trình tìm kiếm sẽ kết thúc.
Nếu đã duyệt tới cuối danh sách mà không có phần tử nào khớp với giá trị cần tìm thì
kết luận dữ liệu tìm kiếm không có trong danh sách.
Giải thuật
● Bắt đầu từ phần tử đầu tiên, so sánh với giá trị muốn tìm, nếu bằng giá trị muốn
tìm thì trả về vị trí hiện tại còn nếu không bằng thì chuyển sang phần tử kế tiếp.
● Nếu đến phần tử cuối cùng mà không tìm thấy giá trị nào bằng thì nghĩa là
không tìm thấy.
Mã giả
Đầu vào: mảng a có N phần tử và giá trị x là giá trị muốn tìm kiếm
Đầu ra: Trả về vị trí nếu tìm thấy phần tử bằng x, ngược lại trả về -1
Bước 1: i = 0 // 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. Trả về i và dừng lại
● 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, trả về -1. Ngược lại: Lặp lại Bước 2.
Ví dụ dưới đây minh họa cách thuật toán tìm kiếm tuyến tính làm việc. Giả sử chúng
ta đang tìm phần tử có giá trị 12 trong mảng sau:
So sánh giá trị phần tử ở vị trí i = 0 với 12.
Vì 48 khác 12 nên chuyển sang so sánh với phần tử ở vị trí tiếp theo i = 1.
Vì 83 khác 12 nên chuyển sang so sánh với phần tử ở vị trí tiếp theo i = 2.
