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

Tìm kiếm nội suy (Interpolation Search)

Tìm kiếm nội suy là một thuật toán tìm kiếm khóa trong một mảng đã được sắp xếp theo giá trị số được gán cho các khóa (giá trị khóa).

Ví dụ:

Giả sử chúng ta có một mảng đã sắp xếp arr[] gồm n giá trị phân bố đều, và chúng ta cần viết một hàm để tìm một phần tử cụ thể target trong mảng.

Thuật toán thực hiện các phép toán sau để tìm vị trí:

// Ý tưởng của công thức là trả về giá trị pos cao hơn

// khi phần tử cần tìm gần với arr[hi]. Và

// giá trị nhỏ hơn khi gần với arr[lo]

pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))

Các khóa:

• arr[] - Mảng nơi các phần tử cần được tìm kiếm
• x - Phần tử cần tìm kiếm
• lo - Chỉ số bắt đầu trong arr[]
• hi - Chỉ số kết thúc trong arr[]

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số làm đối số đầu tiên và một mục tiêu tìm kiếm làm đối số thứ hai.

Hàm nên sử dụng thuật toán tìm kiếm nội suy để tìm mục tiêu trong mảng.

Ví dụ

Dưới đây là mã nguồn:

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31]; const target = 25; const interpolationSearch = (arr = [], target) => {    let left = 0;    let right = arr.length - 1;    while (left <= right) {       const rangeDelta = arr[right] - arr[left];       const indexDelta = right - left;       const valueDelta = target - arr[left];       if (valueDelta < 0) {          return -1;       }       if (!rangeDelta) {          return arr[left] === target ? left : -1;       }       const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);       if (arr[middleIndex] === target) {          return middleIndex;       }       if (arr[middleIndex] < target) {          left = middleIndex + 1;       } else {          right = middleIndex - 1;       }    };    return -1; }; console.log(interpolationSearch(arr, target));

Kết quả

Đầu ra trên console:

10