Алгоритм поиска - 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;
}