CC-6 : Implement Interpolation Search Algorithm.

Description:

The Interpolation search algorithm works on sorted lists, when data values are uniformly distributed in the list. The algorithm estimated the probable index of the element to be searched, using first, last elements and that value to be searched. Given an input array and an element to be searched, search the required element in the input array using Interpolation search.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 67, 77, 96, 122, 144, 201,	122 found at index 6 76 found at index -1 3 found at index 0 201 found at index 8

Pseudocode:

interpolationSearch(nums[], toSearch):

Integer array named nums, and integer named toSearch to be searched are received as input parameters.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to zero, we will use this variable to check the last index of partition in which are searching for required integer.

While (firstIdx <= lastIdx) and toSearch>=nums[firstIdx] and toSearch<=nums[lastIdx] do the following steps:

Set integer variable named increment to ((toSearch-nums[firstIdx]) * (lastIdx-firstIdx)) / (nums[lastIdx]-nums[firstIdx]). This is the formula used to calculate probable index offset of toSearch based on using first, last elements and that value to be searched.

Set currIdx to firstIdx+increment.

If nums[currIdx]==toSearch, return currIdx, as we have found the index of the number that we were searching for.

Else if nums[currIdx]< tosearch:

Set firstIdx to currIdx+1.

Else :

set lastIdx to currIdx-1

If toSearch is not found in code above return -1, as the required element does not exist within the input array.

Code:

public int interpolationSearch(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while ((firstIdx<lastIdx)&&(toSearch>=nums[firstIdx])&&(toSearch<=nums[lastIdx])) {
		int increment=((toSearch-nums[firstIdx])*(lastIdx-firstIdx))/
				(nums[lastIdx]-nums[firstIdx]);
		int currIdx=firstIdx+increment;
		if (nums[currIdx]==toSearch) {
			return currIdx;
		}else { 
			if (nums[currIdx] < toSearch){
				firstIdx=currIdx+1;
			}else {
				lastIdx=currIdx-1;
			}
		}
			
	}	
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchInterpolationSearch {

public int interpolationSearch(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while ((firstIdx<lastIdx)&&(toSearch>=nums[firstIdx])&&(toSearch<=nums[lastIdx])) {
		int increment=((toSearch-nums[firstIdx])*(lastIdx-firstIdx))/
				(nums[lastIdx]-nums[firstIdx]);
		int currIdx=firstIdx+increment;
		if (nums[currIdx]==toSearch) {
			return currIdx;
		}else { 
			if (nums[currIdx] < toSearch){
				firstIdx=currIdx+1;
			}else {
				lastIdx=currIdx-1;
			}
		}
			
	}	
	return -1;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchInterpolationSearch search=new SearchInterpolationSearch();
	int[] nums= { 3,22,44,67,77,96,122, 144, 201};
	int toSearch=122;
	retVal=search.interpolationSearch(nums, toSearch);
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	System.out.println("\n\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=76;
	retVal=search.interpolationSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=3;
	retVal=search.interpolationSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=201;
	retVal=search.interpolationSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
}
		
}

}