#c
#c
Вопрос:
как я могу изменить эти две (или любую из них) функции, чтобы получить минимальное значение dist, где dist=pow(target-v[i],2). Я хочу получить индекс элемента в векторе с наименьшим расстоянием от цели, учитывая, что вектор упорядочен, и я хочу эффективно найти элемент с помощью двоичного поиска. Большое спасибо.
int getClosest(int val1, int val2,int target, int i, int j)
{
if (pow(target - val1,2) >= pow(val2 - target,2))
return j;
else
return i;
}
// Returns element closest to target
int findClosest(vector<int> arr, int n, int target)
{
// Corner cases
if (target <= arr[0])
return 0;
if (target >= arr[n - 1])
return n - 1;
// Doing binary search
int i = 0, j = n, mid = 0;
while (i < j) {
mid = (i j) / 2;
if (arr[mid] == target)
return mid;
/* If target is less than array element,
then search in left */
if (target < arr[mid]) {
// If target is greater than previous
// to mid, return closest of two
if (mid > 0 amp;amp; target > arr[mid - 1])
{
return getClosest(arr[mid - 1],arr[mid], target, mid-1,mid);
}
/* Repeat for left half */
j = mid;
}
// If target is greater than mid
else {
if (mid < n - 1 amp;amp; target < arr[mid 1])
return getClosest(arr[mid], arr[mid 1], target, mid,mid 1);
// update i
i = mid 1;
}
}
// Only single element left after search
return mid;
}
enter code here
Комментарии:
1. Вам не нужна функция питания. Положительные степени чисел получают отношение модулей чисел.
2. Предпочитаю использовать
(x * x)
вместоpow(x,2)
. Умножение часто происходит быстрее, работает с целыми числами и занимает меньше места в коде.
Ответ №1:
Прежде всего, чтобы использовать алгоритм бинарного поиска, вы должны быть уверены в том, что данный массив или вектор отсортированы или нет. Если вектор отсортирован, то только вы можете применить двоичный поиск, чтобы найти индекс ближайшего расстояния.
Теперь, учитывая, что данный вектор отсортирован, мы можем применить двоичный поиск.
Еще одна вещь, которую я вижу в вашем коде, в getClosest(int v1, int v2, int target, int i, int j)
методе, который вы возводите в квадрат с обеих сторон, чтобы проверить положительные целые числа. Скорее вы можете рассмотреть mod operator или abs
метод в cpp для этого. abs
займет меньше времени, чем pow
.
Измененный код:
int getClosest(int val1, int val2,int target, int i, int j)
{
if (abs(target - val1) >= abs(val2 - target))
return j;
else
return i;
}
// Returns element closest to target
int findClosest(vector<int> arr, int n, int target)
{
// Corner cases
if (target <= arr[0])
return 0;
if (target >= arr[n - 1])
return n - 1;
// Doing binary search
int i = 0, j = n, mid = 0;
while (i < j) {
mid = (i j) / 2;
if (arr[mid] == target)
return mid;
/* If target is less than array element,
then search in left */
if (target < arr[mid]) {
// If target is greater than previous
// to mid, return closest of two
if (mid > 0 amp;amp; target > arr[mid - 1])
{
return getClosest(arr[mid - 1],arr[mid], target, mid-1,mid);
}
/* Repeat for left half */
j = mid;
}
// If target is greater than mid
else {
if (mid < n - 1 amp;amp; target < arr[mid 1])
return getClosest(arr[mid], arr[mid 1], target, mid,mid 1);
// update i
i = mid 1;
}
}
// Only single element left after search
return mid;
}