[ Search ] Tìm kiếm tuần tự [Code C++]

in , , , , , /

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
Kết quả là tìm thấy x trong dãy.

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.