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ử a0,a1,a2,…,an-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]
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