SẮP XẾP & TÌM KIẾM
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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

Trong bài này mình sẽ giới thiệu thuật toán Interpolation Search (tìm kiếm nội suy). Đây là một trong những thuật toán tìm kiếm được sử dụng rất nhiều vì tốc độ tìm kiếm rất nhanh và chính xác.

Chúng ta sẽ cùng nhau tìm hiểu về Interpolation Search. Và so sánh nó với Binary Search, để xem sự khác biệt giữa hai cách tìm kiếm này. Sau đó mình sẽ đưa ra thuật toán cho phương pháp tìm kiếm này.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

1. Tìm kiếm nội suy là gì?

Thuật toán tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search. Nó có xu hướng tiến gần đến vị trí, giá trị tìm kiếm. Do đó tốc độ tìm kiếm được tối ưu rất cao và nhanh hơn nhiều so với Binary Search.

Cách thức hoạt động của nó dựa trên Binary Search, nhưng có sự cải tiến hơn. Đó chính là nó tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó để tìm.

Ví dụ:

Chúng ta có danh sách các sinh viên trong một lớp. Nếu chúng ta muốn tìm một bạn tên Tiến, thì chúng ta sẽ ưu tiên việc tìm kiếm từ cuối danh sách. Chứ không nên tìm kiếm từ đầu danh sách vì điều đó rất mất thời gian.

Với Interpolation Search nó sẽ linh hoạt hơn rất nhiều trong lúc tìm kiếm.

2. Thuật toán tìm tiếm nội suy (Interpolation Search)

Giả xử chúng ta có:

  • Left, right là hai vị trí đầu và cuối.
  • T là tập.
  • X là giá trị cần tìm.

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

Bước 1:Chúng ta sẽ sử dụng công thức tìm phần tử chính giữa của tập theo cách tìm kiếm Binary Search:

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

Trong công thức trên chúng ta sẽ thay giá trị 1/2 bằng biểu thức sau:

(X - T[left]) / (T[right] - T[left])

Sau khi thay biểu thức vào công thức sẽ được công thức mới như sau:

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

Bước 2: Bây giờ chúng ta sẽ kiểm tra T[Search] nếu bằng X thì Search chính là vị trí cần tìm.

  • Nếu Search < X thì tăng left lên một đơn vị rồi quay lại bước 1.
  • Nếu Search > X thì giảm right xuống một đơn vị rồi quay lại bước 1.

Thuật toán tìm kiếm Interpolation Search

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;
}

3. Ví dụ tìm kiếm nội suy

Chúng ta sẽ áp dụng thuật toán trên để tìm một phần tử x trong mảng, được nhập từ bàn phím.

Sau khi đã viết được hàm InterPolationSearch(), thì việc đơn giản của chúng ta sẽ là viết hàm Main và gọi nó ra.

Main:

int main()
{
  int arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
  int n = sizeof(arr)/sizeof(arr[0]);
  int x;

  cout<<"Nhập vào số cần tìm trong mảng: ";
  cin>>x;
  int index = InterPolationSearch(arr, n, x);
 
  if (index != -1)
    cout << "Đã tìm thấy số "<<x<< " trong mảng tại vị trí " << index;
  else
    cout << "Không tìm thấy số "<<x<<" trong mảng.";
   
}

Full Code:

#include <iostream>
 using namespace std;
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 arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
  int n = sizeof(arr)/sizeof(arr[0]);
  int x;

  cout<<"Nhập vào số cần tìm trong mảng: ";
  cin>>x;
  int index = InterPolationSearch(arr, n, x);
 
  if (index != -1)
    cout << "Đã tìm thấy số "<<x<< " trong mảng tại vị trí " << index;
  else
    cout << "Không tìm thấy số "<<x<<" trong mảng.";
   
  cout<<"\n---------------------------------------\n";
  cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả 1:

interpolation search PNG

Kêt quả 2:

interpolation search1 PNG

Như vậy là chúng ta đã thực hiện xong chương trình kiểm tra một số có trong mảng. Cũng như kết thúc hướng dẫn thuật toán tìm kiếm Interpolatipon Search. Chúc các bạn thực hiện thành công!!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top