Tìm kiếm tuyến tính:

Ý tưởng là duyệt tuần tự bắt đầu từ phần tử đầu tiên, lần lượt so sánh với key tương ứng cho đến khi gặp phần tử cần tìm hoặc đi hết dãy. Giá trị trả về là vị trí xuất hiện đầu tiên của key trong dãy, nếu ko có thì trả về -1.

Giải thuật tìm kiếm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ.

[codes=c]int timtuyentinh(int a[],int n, int key)  
{  
  for(int i=0; i<n; i++)  
  {  
    if(a[i]==key)  
        return i;  
  }  
  return -1;  
} [/codes]

Tìm kiếm nhị phân:

Áp dụng khi dãy đã được sắp xếp, ý tưởng chính là chia đôi dãy ra để tìm.

Thuật giải nhị phân dựa vào quan hệ giá trị của các phần tử trong mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được với dãy đã có thứ tự.

Thuật giải nhị phân tìm kiếm nhanh hơn tìm kiếm tuyến tính. Tuy nhiên khi áp dụng thuật giải nhị phân thì cần phải quan tâm đến chi phí cho việc sắp xếp mảng. Vì khi mảng được sắp thứ tự rồi thì mới tìm kiếm nhị phân.

[codes=c]int BinarySearch(int a[], int n, int key){
  int left = 0, right = n-1, mid;
  while (left <= right){
    mid = (left + right)/ 2;  // lấy điểm giữa
    if (a[mid] == key)  // nếu tìm được
      return mid;
    if (a[mid] < key)    // tìm đoạn bên phải mid
      left = mid+1;    
    else
      right = mid-1;  // tìm đoạn bên trái mid
  }
  return -1;      // không tìm được
}[/codes]

Last modified on March 31st, 2021 at 12:58 am

10cth1 C