Бинарный поиск

        static void Main(string[] args)
        {
             Console.WriteLine("Введите количество элементов:");
            int num = Convert.ToInt32(Console.ReadLine());
            int[] arr = new int[num]; 
            for (int i = 0; i < num; i++)
            {
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            Console.WriteLine("Ваш массив:");
            foreach (double x in arr)
            {
                System.Console.Write(x + " ");
            }
 
            //сортировка
            Array.Sort(arr);
 
            //вывод отсортированного массива
            Console.WriteLine("\nВаш отсортированный массив:");
 
            foreach (double x in arr)
            {
                System.Console.Write(x + " ");
            }
            BinarySearch(arr, 9, 0, --num);
        }
 
        public static int BinarySearch(int[] arr, int key, int low, int high)
        {
            while (low <= high && key >= arr[low] && key <= arr[high])
            {
                /*usual binary search:
                  int mid = low + (high - low) / 2;
                */
                //linear interpolation binary search
                int mid = low + (key - arr[low]) * ((high - low) / (arr[high] - arr[low]));
                //
                if (key == arr[mid])
                {
                    Console.WriteLine("Иcкомый элемент находится под индексом №" + mid);
                    Console.WriteLine();
                    return mid;
                }
                if (key < arr[mid])
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }
            Console.WriteLine("Искомого числа в данном массиве нет");
            return 0;
        }