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

Tìm kiếm nội suy

Tìm kiếm nội suy là một thuật toán để tìm kiếm một khóa trong một mảng đã được sắp xếp thứ tự theo các 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 được sắp xếp gồm n giá trị được phân phối đồng đều arr [] và chúng ta cần viết một hàm để tìm kiếm một mục tiêu phần tử cụ thể trong mảng.

Nó thực hiện các thao tác sau để tìm vị trí -

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

// khi phần tử cần tìm gần hơn arr [hi]. Và

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

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

Phím -

• arr [] - Mảng nơi các phần tử cần được tìm kiếm

• x - Phần tử được tìm kiếm

• lo - Chỉ mục bắt đầu trong arr []

• chào - Chỉ mục kết thúc trong arr []

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng số làm đối số đầu tiên và 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 kiếm mục tiêu trong mảng.

Ví dụ

Sau đây là mã -

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

Đầu ra

Sau đây là kết quả trên bảng điều khiển -

10