What is? Interpolation search ？

Before introducing interpolation search , Let me first introduce the binary search method , Then combine the comparison between the two , You will understand .

At ordinary times , We often use binary search , To quickly find whether the specified element is in a collection （ Premise is ： The set has been ordered ）

Two points search

First declare the following variables ：

Left position ：left = 0, Right position ： right = len(list) - 1

Find the target element ： target

Sets are arranged in ascending order ;

Find the specific process ：

1. Calculate the middle position ： mid = （left + right）/ 2

2. By comparison target And list [mid] Size to constantly update left and right

•  target == list [mid], The goal is target find
•  target > list [mid], The goal is target stay mid Position right , to update ： left = mid + 1
• target < list [ mid ],  The goal is target stay mid Position left , to update ： right = mid - 1

3. repeat 1 step , Until the cycle conditions are not met ： left <= right

What is Interpolation search

Interpolation search

The difference between it and binary search is ： mid How to calculate the position

that Interpolation search How to calculate the position of further comparison ？

The specific process is ：

// a The calculation of can be understood as ： take left And right Spacing between , Divide equally according to the difference between the rightmost and leftmost elements

a = int(float64(right - left) / float64( list [ right ] - list [ left ]))   

// b The calculation of can be understood as ： target The actual difference from the leftmost element

b = target - list [ left ] 

// Final position That is to say ： The leftmost position add Actual offset interval （ a * b)

position  = left + a * b

The result here is position Equivalent to In binary search mid,

This is a variable speed method of finding position , Efficiency is higher than binary search .

Hope you found something .

See you next time