Introduction
Interpolation search is faster than binary searching but more complex. It works by using data points based on the value being searched.
Example
// Array must be sorted
function interpolationSearch(array: any[], valueToFind: any) {
let low = 0;
let mid = -1;
let high = array.length - 1;
let matchFound = false;
while (!matchFound) {
if (low === high || array[low] === array[high]) {
return -1;
}
mid = Math.floor(
low +
((high - low) / (array[high] / array[low])) *
(valueToFind - array[low]),
);
if (array[mid] === valueToFind) {
return mid;
} else {
if (array[mid] < valueToFind) {
low = mid + 1;
} else if (array[mid] > valueToFind) {
high = mid - 1;
}
}
}
}
const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log('interpolation search', interpolationSearch(arr, 4));
Lesson task
This lesson task is to understand how the interpolation search works.
Goal
To understand how interpolation search works.
Brief
Complete the Level 1 process
NOTE: Lesson tasks do not get submitted on Moodle and are not assessed by tutors. They are mainly there for you to practise what you have learned in the lesson.
Level 1 process
-
Work through the code example above, trying to understand what each line is doing. If you don’t understand then console.log the values.
-
Once you know how interpolation search works, try to create the algorithm yourself.