Program 6 - Interpolation Search

	#include <stdio.h>
	int interpolation_search(int a[], int n, int key){
	int f = 0, l = n-1, mid;
	while(f < l){
	/*Note:
	* I've tried varying the formula a little bit and this is the version
	* which works perfectly in Code Blocks
	* Try it out yourself enter 1,2,3,4,5
	* and search for elements like 6,7,0,etc
	* the original formula results in an infinite loop
	*/
	mid = f + (l - f) * ( (key - a[f]) / (a[l] - a[f]) );
	if(key == a[mid]){
	return mid;
	} else if(key < a[mid]){
	l = mid - 1;
	} else if(key > a[mid]){
	f = mid + 1;
	}
	}
	return -1;
	}
	int main(){
	int a[] = {1,2,3,4,5};
	int n = sizeof(a) / sizeof(a[0]);
	int element;
	printf("Enter element to search: ");
	scanf("%d", &element);
	int pos = interpolation_search(a, n, element);
	if(pos != -1){
	printf("Element found at position: %d\n", pos + 1);
	} else {
	printf("Element not found\n");
	}
	return 0;
	}