Thuật toán tìm kiếm nội suy trong JavaScript

1993

Trong lập trình, tìm kiếm phần tử trong mảng là một bài toán cơ bản với nhiều thuật toán có thể được sử dụng để giải quyết. Tìm kiếm nội suy (Interpolation Search) là một thuật toán được ưu chuộng sử dụng vì tốc độ tìm kiếm rất nhanh và chính xác. Trong bài viết này chúng ta cùng nhau tìm hiểu về thuật toán này và cách triển khai nó trong ngôn ngữ JavaScript nhé.

Tìm kiếm nhị phân

Interpolation Search là một giải thuật tìm kiếm nhanh, một biến thể cải tiến của tìm kiếm nhị phân (Binary Search). 2 giải thuật tìm kiếm này đều dựa trên nguyên tắc chia để trị (Divide and Conquer). Để giải thuật thực hiện được thì mảng đầu vào cần phải được sắp xếp sẵn từ trước.

Để hiểu về tìm kiếm nội suy, trước tiên chúng ta tìm hiểu Binary Search nhé.

Tìm kiếm nhị phân sẽ tìm kiếm một phần tử cụ thể bằng cách so sánh phần tử cần tìm với phần tử ở vị trí giữa (theo chỉ số) của mảng đầu vào:

  • Nếu bằng nhau => trả về kết quả tìm kiếm
  • Nếu phần tử cần tìm lớn hơn => thực hiện lặp lại bước trên với mảng con ở bên phải phần tử ở giữa
  • Nếu phần tử cần tìm nhỏ hơn => thực hiện lặp lại bước trên với mảng con ở bên trái phần tử ở giữa

Tìm kiếm nhị phân

Ở ví dụ trên, chúng ta tìm kiếm giá trị 2 trong mảng số từ 1 đến 10. Sẽ có 4 vòng lặp được thực hiện để tìm ra được giá trị cần tìm.

  5 cách chia một mảng lớn thành nhiều mảng nhỏ trong Javascript

Tìm kiếm nội suy

Ở trong ví dụ của tìm kiếm nhị phân chúng ta thấy rằng giải thuật không quan tâm đến giá trị đầu vào và luôn luôn chia đều mảng thành 2 phần bằng nhau. Thực tế nếu chúng ta đánh giá mảng số đầu vào cùng giá trị tìm kiếm thì có thể nhận thấy giá trị 2 sẽ có nhiều khả năng nằm ở vị trí đầu của mảng số vì nó gần hơn với giá trị bé nhất của mảng là 1 hơn là giá trị lớn nhất của mảng là 10. Nó cũng giống như việc khi chúng ta tra cứu từ điển, nếu cần tra cứu từ “Interpolation” thì chúng ta sẽ ưu tiên mở phần đầu của quyển từ điển hơn (do chữ cái I nằm gần đầu trong bảng chữ cái, cũng là thứ tự sắp xếp của quyển từ điển); ngược lại khi tra cứu từ “Search” thì ưu tiên sẽ là mở đến những trang gần cuối hơn.

Từ ý tưởng này, tìm kiếm nội suy cải tiến tìm kiếm nhị phân bằng cách tính toán trước vị trí dò trong mảng dựa trên giá trị cần tìm theo công thức:

Tìm kiếm nội suy

Trong đó:

  • arr: mảng giá trị cần tìm kiếm
  • low: chỉ mục thấp nhất của mảng
  • high: chỉ mục cao nhất của mảng
  • target: giá trị cần tìm kiếm
  • mid: chỉ số tính toán được để thực hiện so sánh

Chúng ta cùng đi vào ví dụ cụ thể nhé:

Cho mảng số đã được sắp xếp như dưới đây, chúng ta cần tìm kiếm giá trị 18 trong mảng.

Tìm kiếm nội suy

Tìm kiếm nội suy sẽ thực hiện các vòng lặp, với mỗi vòng lặp chúng ta có 2 bước như sau:

Bước 1: Tính toán chỉ số mảng cần so sánh theo công thức

Bước 2: So sánh giá trị cần tìm và phần tử trong mảng theo chỉ số tính toán

  • Nếu bằng nhau => trả kết quả đầu ra
  • Nếu phần tử của mảng có giá trị lớn hơn giá trị cần tìm => thực hiện lặp với mảng con bên trái 
  • Nếu phần tử của mảng có giá trị nhỏ hơn giá trị cần tìm => thực hiện lặp với mảng con bên phải

Về cơ bản thì điểm khác nhau duy nhất giữa tìm kiếm nội suy và tìm kiếm nhị phân chính là bước 1.

Với bài toán trên, giải thuật tìm kiếm nội suy sẽ cần chạy qua 2 vòng lặp như dưới đây:

Tìm kiếm nội suy

Vòng lặp đầu tiên, theo công thức thì mid sẽ cho giá trị được làm tròn là 

mid = 0 + (18 – 10) * (14 – 0) / (47 – 10) = 3

và phần tử trong mảng đưa ra để so sánh là giá trị 16. Do 16 < 18 (giá trị cần tìm) => mảng mới sử dụng sẽ bắt đầu từ 18 (vị trí phần tử thứ 4)

Tìm kiếm nội suy

Vòng lặp thứ 2,

mid = 4 + (18 – 18) * (14 – 4) / (47 – 18) = 0

Kết quả trả về đúng giá trị cần tìm ở vị trí thứ 4 của mảng.

Tham khảo việc làm JavaScript tại Hồ Chí Minh trên TopDev

Triển khai thuật toán trong JavaScript

Tìm kiếm nội suy có cách triển khai trong JavaScript khá đơn giản và dễ hiểu, bạn có thể tham khảo đoạn code dưới đây:

function interpolationSearch(sortedArray, seekElement) {
  let leftIndex = 0;
  let rightIndex = sortedArray.length - 1;
  while (leftIndex <= rightIndex) {
    const rangeDelta = sortedArray[rightIndex] - sortedArray[leftIndex];
    const indexDelta = rightIndex - leftIndex;
    const valueDelta = seekElement - sortedArray[leftIndex];
    if (valueDelta < 0) {
      return -1;
    }
    if (!rangeDelta) {
      return sortedArray[leftIndex] === seekElement ? leftIndex : -1;
    }
    // Tính toán giá trị chỉ số của mảng cần so sánh
    const middleIndex =
      leftIndex + Math.floor((valueDelta * indexDelta) / rangeDelta);
    // trả kết quả nếu tìm được giá trị cần tìm
    if (sortedArray[middleIndex] === seekElement) {
      return middleIndex;
    }
    if (sortedArray[middleIndex] < seekElement) {
      // sử dụng mảng bên phải
      leftIndex = middleIndex + 1;
    } else {
      // sử dụng mảng bên trái
      rightIndex = middleIndex - 1;
    }
  }
  return -1;
}

  Bạn biết gì về thuật toán Radix Sort trong JavaScript?

Độ phức tạp của thuật toán

Tìm kiếm nội suy có độ phức tạp là O(log(log(n))) so với tìm kiếm nhị phân với độ phức tạp là O(log(n)) thì việc cải tiến này khá đáng giá. Giải thuật cũng sẽ hiệu quả hơn với những bài toán mà các phần tử trong mảng được phân bố đều.

Kết bài

Như vậy là chúng ta đã cùng nhau tìm hiểu thuật toán tìm kiếm nội suy Interpolation Search và cách triển khai thuật toán này trong ngôn ngữ lập trình JavaScript. Đây là một thuật toán hay và cũng dễ triển khai trong nhiều ngôn ngữ lập trình khác nhau. Hy vọng bài viết hữu ích dành cho bạn và hẹn gặp lại trong các bài viết tiếp theo của mình.

Tác giả: Phạm Minh Khoa

Có thể bạn quan tâm:

Hàng loạt việc làm IT hấp dẫn trên TopDev đang chờ bạn ứng tuyển..

RELATED ARTICLESMORE FROM AUTHOR