Найдите точку, сумма расстояний которой от всех заданных точек на прямой равна K

Дан отсортированный массив arr[] , состоящий из N целых чисел, представляющих точки на прямой, и целое число K , задача состоит в том, чтобы найти любую точку P между первой и последней точкой, такую, что сумма расстояний всех заданных точек от P равна к К . Если такой точки не существует, то выведите «-1» .

Примеры:

Input: arr[] = {1, 3, 6, 7, 11}, K = 18
Output: 8
Explanation:
Consider the value of P as 8. Therefore, the sum of distance of P(= 8) from all points is (8 – 1) + (8 – 3) + (8 – 6) + (8 – 7) + (11 – 8) = 18( =K) which is equal to the given value K and the point 8 lies between the first(= 1) and the last(= 11) point.

Input: arr[] = {-10, -2, 1, 2}, K= 29
Output: -9

Подход: Данная задача может быть решена на основе наблюдения, что сумма расстояний будет минимальной на медиане массива, а расстояние увеличивается при движении от медианы к любому из концов. Итак, идея состоит в том, чтобы выполнить бинарный поиск в обеих половинах массива и проверить, имеет ли какая-либо точка расстояние, равное K . Выполните следующие шаги, чтобы решить проблему:

• Объявите функцию, которая вычисляет сумму расстояний всех точек от заданной точки.
• Выполните двоичный поиск в правой половине массива следующим образом:
  • Если значение N нечетное, то обновите значение left как arr[N / 2] . В противном случае обновите значение left как arr[N / 2 – 1] + 1 .
  • Если значение N четное, то обновите значение right как arr[N – 1] .
  • Найдите сумму расстояний, скажем, temp от середины = (слева + справа) / 2 и проверьте, равно ли значение temp K или нет. ЕСЛИ найдено, чтобы быть правдой , то выведите значение mid как результат.
  • Если значение K < temp , то обновить значение right как mid – 1 . В противном случае обновите значение left как mid + 1 .
• Выполните бинарный поиск в левой половине массива:
  • Установите значение left = arr[0] и right = arr[N / 2] – 1 .
  • Найдите сумму расстояний, скажем, temp от середины = (слева + справа) / 2 и проверьте, равна ли temp K или нет. Если окажется, что это правда , то в качестве результата выведите значение mid .
  • Если значение K > temp , то обновите значение right = mid – 1 . В противном случае обновите значение left = mid + 1 .
• Если в левой и правой половине значения не найдены, то в качестве результата выведите «-1» .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log ₂ (M – m)), где M — максимальное значение, а m — минимальное значение массива.
Вспомогательное пространство: O(1)