/**/

# 插值搜索

## 位置探测

```mid=Lo + ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])

where -
A   =list
Lo  =Lowest index of the list
Hi  =Highest index of the list
A[n]=Value stored at index n in the list```

## 伪代码

```A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

Set Lo  →  0
Set Mid → -1
Set Hi  →  N-1

While X does not match

if Lo equals to Hi OR A[Lo] equals to A[Hi]
end if

Set Mid = Lo + ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])

if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While

End Procedure```

## C语言代码实现

```#include<stdio.h>

#define MAX 10

// array of items on which linear search will be conducted.
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };

int find(int data) {
int lo = 0;
int hi = MAX - 1;
int mid = -1;
int comparisons = 1;
int index = -1;

while(lo <= hi) {
printf("\nComparison %d\n" , comparisons ) ;
printf("lo : %d, list[%d]=%d\n", lo, lo, list[lo]);
printf("hi : %d, list[%d]=%d\n", hi, hi, list[hi]);

comparisons++;

// probe the mid point
mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) * (data - list[lo]));
printf("mid=%d\n",mid);

// data found
if(list[mid] == data) {
index = mid;
break;
} else {
if(list[mid] < data) {
// if data is larger, data is in upper half
lo = mid + 1;
} else {
// if data is smaller, data is in lower half
hi = mid - 1;
}
}
}

printf("\nTotal comparisons made: %d", --comparisons);
return index;
}

int main() {
//find location of 33
int location = find(33);

// if element was found
if(location != -1)
printf("\nElement found at location: %d" ,(location+1));
else

return 0;
}```

```Comparison 1
lo : 0, list[0]=10
hi : 9, list[9]=44
mid=6

Total comparisons made: 1
Element found at location: 7```

## 猜你喜欢

Java性能调优实战 -〔刘超〕

TensorFlow 2项目进阶实战 -〔彭靖田〕

Web安全攻防实战 -〔王昊天〕

Kubernetes入门实战课 -〔罗剑锋〕