Dada una array de enteros ordenados. Necesitamos encontrar el valor más cercano al número dado. La array puede contener valores duplicados y números negativos.
Ejemplos:
Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9}
Target number = 11
Output : 9
9 is closest to 11 in given array
Input :arr[] = {2, 5, 6, 7, 8, 8, 9};
Target number = 4
Output : 5
Una solución simple es recorrer la array dada y realizar un seguimiento de la diferencia absoluta del elemento actual con cada elemento. Finalmente devuelve el elemento que tiene diferencia de absolución mínima.
Una solución eficiente es usar Binary Search .
Javascript
<script>
// JavaScript program to find element
// closest to given target.
// Returns element closest to target in arr[]
function findClosest(arr, target)
{
let n = arr.length;
// Corner cases
if (target <= arr[0])
return arr[0];
if (target >= arr[n - 1])
return arr[n - 1];
// Doing binary search
let i = 0, j = n, mid = 0;
while (i < j)
{
mid = (i + j) / 2;
if (arr[mid] == target)
return arr[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 && target > arr[mid - 1])
return getClosest(arr[mid - 1],
arr[mid], target);
// Repeat for left half
j = mid;
}
// If target is greater than mid
else
{
if (mid < n - 1 && target < arr[mid + 1])
return getClosest(arr[mid],
arr[mid + 1],
target);
i = mid + 1; // update i
}
}
// Only single element left after search
return arr[mid];
}
// Method to compare which one is the more close
// We find the closest by taking the difference
// between the target and both values. It assumes
// that val2 is greater than val1 and target lies
// between these two.
function getClosest(val1, val2, target)
{
if (target - val1 >= val2 - target)
return val2;
else
return val1;
}
// Driver Code
let arr = [ 1, 2, 4, 5, 6, 6, 8, 9 ];
let target = 11;
document.write(findClosest(arr, target));
// This code is contributed by code_hunt
</script>
Producción:
9
Complejidad del tiempo: O(log(n))
Espacio auxiliar: O(log(n)) (se crea una pila implícita debido a la recursividad)
¡ Consulte el artículo completo sobre Encontrar el número más cercano en la array para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA