Алгоритм поиска - C# (190011)

Узнай цену своей работы

Формулировка задачи:

Ребят помогите с задание. Не могу понять что нужно сделать! Оптимизированный двоичный поиск. В процессе деления выбрать не середину интервала, а значение, вычисленное из предположения о линейном возрастании значений элементов массива в текущем интервале поиска. Сравнить эффективности разработанного и базового алгоритмов на массивах с резко неравномерным возрастанием значений (например, 1, 2, 2, 3, 4, 25).

Решение задачи: «Алгоритм поиска»

textual
Листинг программы
        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) / 2;
 
                //linear interpolation binary search
                int mid = low + (key - arr[low]) * ((high - low) / (arr[high] - arr[low])); 
 
                //
                if (key == arr[mid])
                {
                    return mid;
                }
                if (key < arr[mid])
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }
            return -1;
        }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 4 из 5
Похожие ответы