Интерполяционный поиск. Помогите исправить код пожалуйста

class Program
    {
        static void Main(string[] args)
        {
            Random rnd = new Random();
            int[] array = new int[10];
            Console.WriteLine("Исходный массив");
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = rnd.Next(1000);
                Console.WriteLine(array[i]);
            }
            BinarySort(ref array);
            Console.WriteLine("Сортированный массив");
            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine(array[i]);
            }
            
            Console.WriteLine("Какое число найти:");
            int iVal = int.Parse(Console.ReadLine());
            Console.WriteLine($"Index: {Array.BinarySearch(array, iVal)}");

            Console.WriteLine("интерполяционный поиск\nКакое чичсло найти:");
            int iVal1 = int.Parse(Console.ReadLine());
            Console.WriteLine($"Index: {(interpolationSearch(array, iVal1))}");


            Console.ReadLine();
        }
        static void BinarySort(ref int[] array)
        {
            List<int> sort = new List<int>();
            int index;
            for (int i = 0; i < array.Length; i++)
            {
                index = FindIndex(sort, array[i]);
                sort.Insert(index, array[i]);
            }
            array = sort.ToArray();
        }
        static int FindIndex(List<int> arr, int el)
        {
            if (arr.Count == 0)
            {
                return 0;
            }
            if (arr[arr.Count - 1] < el)
            {
                return arr.Count;
            }
            int i = 0;
            int j = arr.Count;
            while (i + 1 < j)
            {
                int middle = i + (j - i) / 2;
                if (arr[middle] >= el)
                {
                    j = middle;
                }
                else
                {
                    i = middle;
                }
            }
            return arr[i] >= el ? i : j;
        }
        static int interpolationSearch(int[] array, int soughtElement)
        {
            int start = 0;
            int end = array.Length - 1;
            if (array[end] == soughtElement)
                return end;
            if (array[start] == soughtElement)
                return start;
            while (array[start] < soughtElement && array[end] > soughtElement)
            {
                if (array[start] == array[end])
                    break;
                int middle = start + ((soughtElement - array[start]) * (end - start)) /
               (array[end] - array[start]);
                int middleEl = array[middle];
                if (middleEl < soughtElement)
                    start = middle + 1;
                else if (middleEl > soughtElement)
                    end = middle - 1;
                else
                    return middle;
            }
            return -1;
        }


    }

Задание, нужно сделать программу, которая будет выполнять бинарный поиск и интерполяционный. С бинарным поиск я справился, ищет все как надо, а вот интерполяционный поиск, находит идекс только первого и последнего массива, другие выдает : -1