LATEST

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++. Đây là một trong những thuật toán tìm kiếm được sử dụng nhiều nhất, bởi nó nhanh hơn và chính xác hơn bất kì thuật toán tìm kiếm nào.

Trước khi đi vào tìm hiểu thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++, chúng ta hãy xem khái niệm về nó đã nhé. Sau đó mình sẽ giải thích thuật toán và kèm theo ví dụ minh họa cho các bạn tham khảo.

Tìm kiếm nội suy (Interpolation Search) là gì?

Thuật toán tìm kiếm nội suy (Interpolation Search) là sự cải tiến của thuật toán tìm kiếm nhị phân (Binary Search). Tuy nhiên nó linh động hơn rất nhiều so với tìm kiếm nhị phân.

Nói một cách dễ hiểu hơn, tìm kiếm nhị phân chia nữa mảng bắt đầu từ đầu mảng đến cuối mảng. Tìm kiếm nội suy (Interpolation Search) sẽ tìm ra phần tử gần giá trị tìm kiếm nhất và bắt đầu tìm từ đó.

Như vậy thời gian tìm kiếm nhanh hơn và phạm vi tìm kiếm được thu hẹp hơn rất nhiều.

bai10 01 png

Ví dụ: Mình có một mảng Number = {4, 5, 6, 7, 10}. Bây giờ cần tìm giá trị 7 trong mảng Number.

  • Nếu sử dụng thuật toán tìm kiếm nhị phân thì bắt đầu tìm từ số 4 (đầu mảng).
  • Đối với tìm kiếm nội suy (Interpolation Search) thì nó sẽ so sánh và bắt đầu tìm từ cuối, vì như vậy sẽ nhanh hơn.

Ví dụ thực tế: Giả sử chúng ta muốn tìm kiếm bạn Tâm trong danh sách lớp. Chúng ta ưu tiên tìm từ cuối danh sách thay vì tìm từ đầu danh sách. Như vậy sẽ nhanh hơn rất nhiều.

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Bởi vì thuật toán tìm kiếm nội suy (Interpolation Search) được cải tiến từ thuật toán tìm kiếm nhị phân, nên về cơ bản khá giống nhau. Mảng cần được sắp xếp trước khi tìm kiếm nhé.

Dưới đây là thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++, các bạn hãy xem qua rồi mình giải thích ngay bên dưới nhé.

int InterPolationSearch(int arr[], int n, int x)
{
  int left = 0;
  int right = n-1;
  while (left <= right && x >= arr[left] && x <= arr[right])
  {
    double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
    int val2 = (right-left);
    int Search = left + val1*val2;
  
    if (arr[Search] == x)
      return Search;
  
    if (arr[Search] < x)
      left = Search + 1;
    else
      right = Search - 1;
  }
  return -1;
}

Trong thuật toán này, chúng ta thay đổi công thức tìm phần tử ở giữa khác một chút so với thuật toán tìm kiếm nhị phân như sau.

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

Search = left + (right - left) * 1/2

Tìm kiếm nội suy:

Search = left + (X- T[left]) * (right – left) / (T[right] – T[left])

Giải thích thuật toán:

  • Sau khi xác định được phần tử giữa (middle), ta so sánh với giá trị cần tìm. Nếu bàng nhau thì trả về vị trí rồi thoát vòng lặp.
  • Nếu Search < x thì tăng left lên 1 đơn vị rồi quay lại vòng lặp.
  • Nếu Search > x thì giảm right xuống một đơn vị rồi quay lại vòng lặp.

Bây giờ mình sẽ thực hiện một ví dụ cụ thể sử dụng thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++. Chương trình được viết bằng hai ngôn ngữ C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>

void sort_numbers_ascending(int number[], int count)
{
   int temp, i, j, k;
   for (j = 0; j < count; ++j)
   {
      for (k = j + 1; k < count; ++k)
      {
         if (number[j] > number[k])
         {
            temp = number[j];
            number[j] = number[k];
            number[k] = temp;
         }
      }
   }
   printf("Các số sau khi được sắp xếp tăng dần: ");
   for (i = 0; i < count; ++i)
      printf("%d ",number[i]);
}

int InterPolationSearch(int arr[], int n, int x)
{
  int left = 0;
  int right = n-1;
  while (left <= right && x >= arr[left] && x <= arr[right])
  {
    double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
    int val2 = (right-left);
    int Search = left + val1*val2;
  
    if (arr[Search] == x)
      return Search;
  
    if (arr[Search] < x)
      left = Search + 1;
    else
      right = Search - 1;
  }
  return -1;
}

int main(void) {
  int n,x, result;
    do{
      printf("Nhập vào số lượng phần tử của mảng: ");
      scanf("%d", &n);
      if(n <= 0) printf("Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n");
    }while(n <= 0);
    
    int a[n];
    //nhập các phần tử mảng
    for(int i=0; i<n; i++){
         printf("Nhập vào phần tử a[%d]: ",i);
         scanf("%d",&a[i]);
    }
    
    sort_numbers_ascending(a,n);
  
    printf("\nNhập giá trị x cần tìm: ");
    scanf("%d", &x);
    result = InterPolationSearch(a, n, x);
    if(result == -1) printf("\nKhông tìm thấy giá trị %d trong mảng.\n",x);
    else printf("\nĐã tìm thấy giá trị %d tại vị trí %d",x,result);

    printf("\n----------------------------\n");
    printf("Chương trình này được đăng tại codehow.net");
  return 0;
}

Kết quả:

bai10 03 png

Chương trình C++:

#include <iostream>
using namespace std;

void sort_numbers_ascending(int number[], int count)
{
   int temp, i, j, k;
   for (j = 0; j < count; ++j)
   {
      for (k = j + 1; k < count; ++k)
      {
         if (number[j] > number[k])
         {
            temp = number[j];
            number[j] = number[k];
            number[k] = temp;
         }
      }
   }
   cout<<"Các số sau khi được sắp xếp tăng dần: ";
   for (i = 0; i < count; ++i)
      cout<< number[i]<<" ";
}

int InterPolationSearch(int arr[], int n, int x)
{
  int left = 0;
  int right = n-1;
  while (left <= right && x >= arr[left] && x <= arr[right])
  {
    double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
    int val2 = (right-left);
    int Search = left + val1*val2;
  
    if (arr[Search] == x)
      return Search;
  
    if (arr[Search] < x)
      left = Search + 1;
    else
      right = Search - 1;
  }
  return -1;
}

int main() {
  int n,x, result;
    do{
      cout << "Nhập vào số lượng phần tử của mảng: ";
      cin >> n;
      if(n <= 0) cout<<"Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n";
    }while(n <= 0);
    
    int a[n];
    //nhập các phần tử mảng
    for(int i=0; i<n; i++){
         cout << "Nhập vào phần tử a[" << i << "]: ";
         cin >> a[i];
    }
    sort_numbers_ascending(a,n);
  
    cout<<"\nNhập giá trị x cần tìm: ";
    cin>>x;
    result = InterPolationSearch(a, n, x);
    if(result == -1) cout<<"Không tìm thấy giá trị "<<x<<" trong mảng.\n";
    else cout<<"Đã tìm thấy giá trị "<<x<<" tại vị trí "<<result;

    cout<<"\n----------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

bai10 02 png

Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++. Các bạn hãy luyện tập thật nhiều để sử dụng các thuật toán một cách thành thạo nhé. Chúc các bạn thành công !!!!

Cùng chuyên mục:

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy đuôi (Tail Recursion) trong C / C++

Đệ quy đuôi (Tail Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tìm ước chung lớn nhất trong C / C++

Thuật toán tìm ước chung lớn nhất trong C / C++

Top