4. Interpolation Search(보간 검색)

보간 검색은 정렬된 배열의 값이 균일하게 분포되는 인스턴스에 대한 이진 검색 보다 향상된 기능 입니다. 이진 검색은 항상 중간 요소로 이동하여 확인합니다. 반면, 보간 검색은 검색되는 키의 값에 따라 다른 위치로 갈 수 있다. 예를 들어, 키의 값이 마지막 요소에 가까울 경우 보간 검색은 끝쪽으로 검색을 시작하기 쉽습니다.


// 수식의 개념은
검색할 요소가arr[hi]에 가까울 때 //pos의 더 높은 값을 반환하는 것입니다.그리고
//arr[lo]에 가까울 때 더 작은 값
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
arr[] ==> 요소를 검색해야 하는 배열
x ==>검색할요소
lo ==> arr[]의 시작 인덱스
hi ==> arr[]의 끝 인덱스


배열의 요소가 선형으로 분포되어 있다고 가정해 보겠습니다. 

일반 방정식: y = m*x + c. 
y는 배열의 값이고 x는 인덱스입니다. 

이제 방정식 
arr[hi] = m*hi+c ----(1) 
arr[lo] = m*lo+c ----(2) 
x = m* 에 lo,hi 및 x의 값을 입력합니다 . pos + c ----(3) 

m = (arr[hi] - arr[lo] )/ (hi - lo) 

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

Interpolation 알고리즘의 나머지 알고리즘은 위의 파티션 로직을 제외하고는 동일합니다.

1단계:

루프에서 프로브 위치 공식을 사용하여 "pos" 값을 계산합니다.

2단계:

일치하는 경우 항목의 인덱스를 반환하고 종료합니다.

3단계:

항목이 arr[pos]보다 작으면 왼쪽 하위 배열의 프로브 위치를 계산합니다. 그렇지 않으면 오른쪽 하위 배열에서 동일하게 계산합니다.

4단계:

일치하는 항목을 찾거나 하위 배열이 0으로 줄어들 때까지 반복합니다.

다음은 알고리즘의 구현입니다.


// Javascript program to implement Interpolation Search
 
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
 
function interpolationSearch(arr, lo, hi, x){
  let pos;
   
  // Since array is sorted, an element present
  // in array must be in range defined by corner
   
  if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
     
    // Probing the position with keeping
    // uniform distribution in mind.
    pos = lo + Math.floor(((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));;
     
    // Condition of target found
        if (arr[pos] == x){
          return pos;
        }
  
        // If x is larger, x is in right sub array
        if (arr[pos] < x){
          return interpolationSearch(arr, pos + 1, hi, x);
        }
  
        // If x is smaller, x is in left sub array
        if (arr[pos] > x){
          return interpolationSearch(arr, lo, pos - 1, x);
        }
    }
    return -1;
}
 
// Driver Code
let arr = [10, 12, 13, 16, 18, 19, 20, 21,
           22, 23, 24, 33, 35, 42, 47];
 
let n = arr.length;
 
// Element to be searched
let x = 18
let index = interpolationSearch(arr, 0, n - 1, x);
 
// If element was found
if (index != -1){
   document.write(`Element found at index ${index}`)
}else{
   document.write("Element not found");
}