CREATE OWN LIBRARY

Interpolation search can be described as an improved variation of binary search. This searching technique is known as the extrapolation search. This particular algorithm works based on the probing position of the required value. The list should be sorted to perform the interpolation search. In each step of this searching technique, the remaining search space for the value to be found is calculated. The calculation is done based on the values at the bounds of the search space and the value to be searched. To find the position of the searched element the following formula is used:

Position = lower index + [ (searched element-array [lower index]) * (upper index – lower index) / (array [higher index] – array [lower index])

If the item is matched with the then the position will be printed.

If the item is less than array[position], calculate the probe position again for the left sub-array, and if greater than then the position is calculated for the right sub-array.

These steps will be repeated until we get a match or the sub-arrays will be reduced to 0.

EXAMPLE:

Let the list is:

The searched element be 14

First the lower index = 0

Upper index = 5

Position= 0 + [(14 - 14) *(5 - 0)/ (90 - 14)]

               = 0 + [ 0*5/76]

               = 0 + [0/76]

               = 0

The element at index 0 is 14 which is matched with the searched element so the position will be printed.

INPUT: Array elements
OUTPUT: the index of the array if found
PROCESS:
Step 1: [taking the input]
	Read n [number of elements]
	For i=0 to n-1 repeat
		Read a[i]
	[end of ‘for’ loop]
	Read x [the element which is to be searched]
Step 2: [searching the element]
	Set l<-0
	Set h<-n-1
	While l≤h and x≥a[l] and x≤a[h] repeat
		If l=h then
			If a[l]=x then
				Print “Element x is found at position l+1”
			Else
				Print “Element not found”
			[End of if]
			Return
		[End of ‘if’]
		Set pos<- l+(((h-l)/(a[h]-a[l]))*(x-a[l]))
		If a[pos]=x then
			Print “Element x is found at index pos”
			Return
		[End of ‘if’]
		If a[pos]<x then
			Set l<-pos+1
		Else
			Set h<-pos-1
		[End of ‘if’]
	[End of ‘while’]
Step 3: Stop.