Tìm kiếm nội suy trong C

Tìm kiếm nội suy (Interpolation Search) là biến thể cải tiến của Tìm kiếm nhị phân (Binary Search). Để giải thuật tìm kiếm này làm việc chính xác thì tập dữ liệu phải được sắp xếp.

Binary Search có lợi thế lớn về độ phức tạp thời gian khi so sánh với Linear Search. Linear Search có độ phức tạp trường hợp xấu nhất là Ο(n) trong khi Binary Search là Ο(log n).

Có một số tình huống mà vị trí của dữ liệu cần tìm có thể đã được biết trước. Ví dụ, trong trường hợp danh bạ điện thoại, nếu chúng ta muốn tìm số điện thoại của Hương chẳng hạn. Trong trường hợp này, Linear Search và cả Binary Search có thể là chậm khi thực hiện tìm kiếm, khi mà chúng ta có thể trực tiếp nhảy tới phần không gian bộ nhớ có tên bắt đầu với H được lưu giữ.

Chương trình minh họa tìm kiếm nội suy trong C

#include<stdio.h>

#define MAX 10

// khai bao mot mang 
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };

int find(int data) {
   int lo = 0;
   int hi = MAX - 1;
   int mid = -1;
   int comparisons = 1;      
   int index = -1;

   while(lo <= hi) {
      printf("\nSo sanh lan thu %d  \n" , comparisons ) ;
      printf("lo : %d, list[%d] = %d\n", lo, lo, list[lo]);
      printf("hi : %d, list[%d] = %d\n", hi, hi, list[hi]);
      
      comparisons++;

      // phan tu chot (probe) tai vi tri trung vi
      mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) * (data - list[lo]));
      printf("Vi tri trung vi = %d\n",mid);

      // tim thay du lieu
      if(list[mid] == data) {
         index = mid;
         break;
      }else {
         if(list[mid] < data) {
            // neu du lieu co gia tri lon hon, tim du lieu trong phan lon hon 
            lo = mid + 1;
         }else {
            // neu du lieu co gia tri nho hon, tim du lieu trong phan nho hon 
            hi = mid - 1;
         }
      }               
   }
   
   printf("\nTong so phep so sanh da thuc hien: %d", --comparisons);
   return index;
}

int main() {
   //Tim vi tri cua phan tu 33
   int location = find(33);

   // Neu tim thay phan tu 
   if(location != -1)
      printf("\nTim thay phan tu tai vi tri: %d" ,(location+1));
   else
      printf("Khong tim thay phan tu.");
   
   return 0;
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.