Thuật toán tìm kiếm tuần tự - Sequential search
Ý tưởng thuật toán: xét dãy số cần tìm có n phần tử: a[0], a[1], a[2], ... , a[n-1]. Giá trị cần tìm là x.
- Bắt đầu từ khoá đầu tiên, lần lượt so sánh khoá x với khoá tương ứng trong dãy.
- Quá trình tìm kiếm kết thúc khi tìm được khoá thoả mãn hoặc đi đến hết dãy hoặc gặp điều kiện dừng vòng lặp.
Ví dụ: Cho dãy số a[]={1,25,6,5,2,37,40}; tìm phần tử x=37
Cài đặt thuật toán:
Có 2 thuật toán tìm tuần tự trên dãy khoá đầu vào khác nhau.
[Code Turbo C++]
+ Trên dãy khoá chưa sắp xếp
int SequentialSearch(int x, int a[],int n){
int i =1;
while (i <n &&a[i]!=x)
i = i+1;
return (i); // nếu giá trị trả về là i<=n-1 (tìm thấy), i=n (không tìm thấy)
}
+ Trên dãy khoá đã được sắp xếp
int SequentialSearch (int x, int a[], int n){
int i =1;
while (i <=n && a[i]<x) i = i+1;
if (a[i]==x) return 1;
else return 0; // giá trị trả về là 1 (tìm thấy), 0 (không tìm thấy)
}
// Đề nghị độc giả viết tiếp các hàm còn lại để thực thi các thuật toán trên.
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
Chúc các bạn thành công!