Question

How to implement interpolation search in C#

Answer 1

using System;

public class Program
{
	private static int interpolation_search(int[] arr, int item) {
		int low = 0;
		int high = arr.Length - 1;
		int mid = -1;
		int index = -1;

		while (low <= high) {
			mid = low + (((high - low) / (arr[high] - arr[low])) * (item - arr[low]));

			if (arr[mid] == item) {
				index = mid;
				break;
			}
			else {
				if (arr[mid] < item) {
					low = mid + 1;
				}
				else {
					high = mid - 1;
				}
			}
		}

		return index;
	}
	public static void Main(string[] args)
	{
		int[] arr = new int[] {2, 5, 6, 8, 9, 12, 36, 40, 46, 51, 55, 61, 72, 86, 97};
		int item = 51;

		int index = interpolation_search(arr, item);

		if (index != -1) {
			Console.Write("index = " + index);
		}
		else {
			Console.Write("Not found");
		}
	}
}





/*
run:

index = 9

*/

 

70+ SQL courses for beginners and professionals