JavaScript의 보간 검색

보간 검색

보간 검색은 키에 할당된 숫자 값(키 값)으로 정렬된 배열에서 키를 검색하는 알고리즘입니다.

예를 들어

n개의 균일하게 분포된 값 arr[]의 정렬된 배열이 있고 배열에서 특정 요소 대상을 검색하는 함수를 작성해야 한다고 가정합니다.

위치를 찾기 위해 다음 작업을 수행합니다 -

// 공식의 아이디어는 pos의 더 높은 값을 반환하는 것입니다.

// 검색할 요소가 arr[hi]에 가까울 때. 그리고

// arr[lo]

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

키 -

• arr[] - 요소를 검색해야 하는 배열

• x - 검색할 요소

• lo - arr[]

  의 시작 인덱스

• hi - arr[]

  의 끝 인덱스

숫자 배열을 첫 번째 인수로, 검색 대상을 두 번째 인수로 취하는 JavaScript 함수를 작성해야 합니다.

함수는 배열에서 대상을 검색하기 위해 보간 검색 알고리즘을 사용해야 합니다.

예시

다음은 코드입니다 -

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

출력

다음은 콘솔의 출력입니다 -

10