Continuing with the number guessing game — for numbers 1 to 100, if you already know the result, using binary search might not be the most efficient approach. So what method should we use instead?
Concept
Interpolation Search: This is an algorithm based on binary search. The list being searched must be sorted beforehand, and the data distribution should ideally be linear. If the data is not linearly distributed, the search may result in O(n) performance, which could be even slower than binary search.
Formula: lowIndex + (target - array[lowIndex]) * (highIndex - lowIndex) / (array[highIndex] - array[lowIndex])
- lowIndex: Lower bound index
- highIndex: Upper bound index
- target: The target value to search for
Complexity
- Time complexity: O(n)
- Space complexity: O(1)
Examples
Go
package main
import "fmt"
func interpolationSearch(list []int, target int) int {
low := 0
high := len(list) - 1
for high >= low {
i := low + (target-list[low])*(high-low)/(list[high]-list[low])
if i > high || i < low {
break
}
if target == list[i] {
return i
} else if target > list[i] {
low = i + 1
} else {
high = i - 1
}
}
return -1
}
func main() {
fmt.Println(interpolationSearch([]int{1, 2, 3, 4, 5}, 3)) // 2
fmt.Println(interpolationSearch([]int{1, 2, 3, 4, 5}, 6)) // -1
}
C#
class Algorithm
{
public static int interpolationSearch(int[] list, int target)
{
var low = 0;
var high = list.Length - 1;
while (high >= low)
{
var i = low + (target - list[low]) * (high - low) / (list[high] - list[low]);
if (i > high || i < low)
{
break;
}
if (target == list[i])
{
return i;
}
else if (target > list[i])
{
low = i + 1;
}
else
{
high = i - 1;
}
}
return -1;
}
public static void Main(String[] args)
{
Console.WriteLine(interpolationSearch(new int[] {1, 2, 3, 4, 5}, 3)); // 2
Console.WriteLine(interpolationSearch(new int[] {1, 2, 3, 4, 5}, 6)); // -1
}
}
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
