Блог

как я могу изменить эти две (или любую из них) функции, чтобы получить минимальное значение 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
 

Прежде всего, чтобы использовать алгоритм бинарного поиска, вы должны быть уверены в том, что данный массив или вектор отсортированы или нет. Если вектор отсортирован, то только вы можете применить двоичный поиск, чтобы найти индекс ближайшего расстояния.

Теперь, учитывая, что данный вектор отсортирован, мы можем применить двоичный поиск.

Еще одна вещь, которую я вижу в вашем коде, в 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;
}