obter o número mais próximo fora do array

Eu tenho um número de menos 1000 para mais 1000 e eu tenho uma matriz com números nele. Como isso:

[2, 42, 82, 122, 162, 202, 242, 282, 322, 362] 

Eu quero que o número que eu tenho muda para o número mais próximo da matriz.

Por exemplo eu recebo 80 como o número que eu quero obter 82 .

Aqui está o pseudocódigo que deve ser convertível em qualquer linguagem procedural:

 array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362] number = 112 print closest (number, array) def closest (num, arr): curr = arr[0] foreach val in arr: if abs (num - val) < abs (num - curr): curr = val return curr 

Ele simplesmente elimina as diferenças absolutas entre o número dado e cada elemento da matriz e retorna um dos que têm a mínima diferença.

Para os valores de exemplo:

 number = 112 112 112 112 112 112 112 112 112 112 array = 2 42 82 122 162 202 242 282 322 362 diff = 110 70 30 10 50 90 130 170 210 250 | +-- one with minimal absolute difference. 

Como prova de conceito, aqui está o código Python que usei para mostrar isso em ação:

 def closest (num, arr): curr = arr[0] for index in range (len (arr)): if abs (num - arr[index]) < abs (num - curr): curr = arr[index] return curr array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362] number = 112 print closest (number, array) 

E, se você realmente precisar disso em Javascript, veja abaixo um arquivo HTML completo que demonstra a function em ação:

       

Agora, tenha em mente que pode haver espaço para maior eficiência se, por exemplo, seus itens de dados forem classificados (isso pode ser inferido a partir dos dados de amostra, mas você não os declara explicitamente). Você poderia, por exemplo, usar uma pesquisa binária para encontrar o item mais próximo.

Você também deve ter em mente que, a menos que precise fazer isso várias vezes por segundo, as melhorias de eficiência serão praticamente imperceptíveis, a menos que seus conjuntos de dados fiquem muito maiores.

Se você quiser tentar desse jeito (e pode garantir que o array seja classificado em ordem crescente), este é um bom ponto de partida:

       

Ele basicamente usa o bracketing e a verificação do valor do meio para reduzir o espaço da solução pela metade para cada iteração, um algoritmo O(log N) clássico, enquanto a pesquisa sequencial acima era O(N) :

 0 1 2 3 4 5 6 7 8 9 < - indexes 2 42 82 122 162 202 242 282 322 362 <- values LMHL=0, H=9, M=4, 162 higher, H<-M LMHL=0, H=4, M=2, 82 lower/equal, L<-M LMHL=2, H=4, M=3, 122 higher, H<-M LHL=2, H=3, difference of 1 so exit ^ | H (122-112=10) is closer than L (112-82=30) so choose H 

Como dito, isso não deve fazer muita diferença para conjuntos de dados pequenos ou para coisas que não precisam ser incrivelmente rápidas, mas é uma opção que você pode querer considerar.

Versão ES5:

 var counts = [4, 9, 15, 6, 2], goal = 5; var closest = counts.reduce(function(prev, curr) { return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); }); console.log(closest); 

ES6 (2015) Versão:

 const counts = [4, 9, 15, 6, 2]; const goal = 5; counts .reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); 

Para reutilização, você pode include uma function curry que suporte placeholders ( http://ramdajs.com/0.19.1/docs/#curry ou https://lodash.com/docs#curry ). Isso dá muita flexibilidade dependendo do que você precisa:

 const getClosest = curry((counts, goal) => { return counts .reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); }); const closestTo5 = getClosest(_, 5); const closestTo = getClosest([4, 9, 15, 6, 2]); 

Código de trabalho como abaixo:

 var array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; function closest(array,num){ var i=0; var minDiff=1000; var ans; for(i in array){ var m=Math.abs(num-array[i]); if(m 

Para matrizes ordenadas (pesquisa linear)

Todas as respostas até agora se concentram em pesquisar toda a matriz. Considerando que sua matriz já está classificada e você realmente deseja apenas o número mais próximo, esta é provavelmente a solução mais rápida:

 var a = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; var target = 90000; /** * Returns the closest number from a sorted array. **/ function closest(arr, target) { if (!(arr) || arr.length == 0) return null; if (arr.length == 1) return arr[0]; for (var i=1; i target) { var p = arr[i-1]; var c = arr[i] return Math.abs( p-target ) < Math.abs( c-target ) ? p : c; } } // No number in array is bigger so return the last. return arr[arr.length-1]; } // Trying it out console.log( closest(arr, target) ); 

Note que o algoritmo pode ser amplamente melhorado, por exemplo, usando uma tree binária.

Funciona com matrizes não classificadas

Embora algumas boas soluções tenham sido postadas aqui, o JavaScript é uma linguagem flexível que nos fornece ferramentas para resolver um problema de muitas maneiras diferentes. Tudo se resume ao seu estilo, é claro. Se seu código é mais funcional, você encontrará a variação de redução adequada, ou seja:

  arr.reduce(function (prev, curr) { return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); }); 

No entanto, alguns podem achar isso difícil de ler, dependendo do estilo de codificação. Por isso, proponho uma nova maneira de resolver o problema:

  var findClosest = function (x, arr) { var indexArr = arr.map(function(k) { return Math.abs(k - x) }) var min = Math.min.apply(Math, indexArr) return arr[indexArr.indexOf(min)] } findClosest([2, 42, 82, 122, 162, 202, 242, 282, 322, 362], 80) // Outputs 82 

Ao contrário de outras abordagens que encontram o valor mínimo usando Math.min.apply , este não requer que o array de input seja classificado . Não precisamos nos preocupar com os índices ou classificá-los de antemão.

Vou explicar o código linha por linha para maior clareza:

  1. arr.map(function(k) { return Math.abs(k - x) }) Cria um novo array, essencialmente armazenando os valores absolutos dos números fornecidos (number in arr ) menos o número de input ( x ). Procuraremos o menor número próximo (que também é o mais próximo do número de input)
  2. Math.min.apply(Math, indexArr) Esta é uma maneira legítima de encontrar o menor número na matriz que acabamos de criar antes (nada mais)
  3. arr[indexArr.indexOf(min)] Esta é talvez a parte mais interessante. Encontramos nosso menor número, mas não temos certeza se devemos adicionar ou subtrair o número inicial ( x ). Isso porque usamos Math.abs() para encontrar a diferença. No entanto, array.map cria (logicamente) um mapa da matriz de input, mantendo os índices no mesmo lugar. Portanto, para descobrir o número mais próximo, retornamos o índice do mínimo encontrado na matriz fornecida indexArr.indexOf(min) .

Eu criei um bin demonstrando isso.

Esta é uma proposta com um quantificador existencial ES5, Array#some , que permite interromper a iteração se uma condição for atendida.

Opposit of Array#reduce , não precisa iterar todos os elementos para um resultado.

Dentro do retorno de chamada, um delta absoluto entre o valor pesquisado e o item real é obtido e comparado com o último delta. Se maior ou igual, a iteração é interrompida, porque todos os outros valores com seus deltas são maiores que o valor real.

Se o delta no retorno de chamada for menor, o item real será atribuído ao resultado e o delta será lastDelta .

No resultado, valores menores com deltas iguais são obtidos, como no exemplo abaixo de 22 , que resulta em 2 .

Se houver uma prioridade de valores maiores, a verificação delta deve ser alterada de

 if (delta >= lastDelta) { 

para

 if (delta > lastDelta) { // ^^^ without equal sign 

Isso iria ficar com 22 , o resultado 42 (prioridade de valores maiores).

Essa function precisa de valores classificados na matriz.


Código com prioridade de valores menores:

 function closestValue(array, value) { var result, lastDelta; array.some(function (item) { var delta = Math.abs(value - item); if (delta >= lastDelta) { return true; } result = item; lastDelta = delta; }); return result; } var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; console.log(21, closestValue(data, 21)); // 2 console.log(22, closestValue(data, 22)); // 2 smaller value console.log(23, closestValue(data, 23)); // 42 console.log(80, closestValue(data, 80)); // 82 

Não sei se devo responder a uma pergunta antiga, mas como esse post aparece primeiro nas pesquisas do Google, esperei que você me perdoasse adicionando minha solução e meu 2c aqui.

Sendo preguiçoso, eu não podia acreditar que a solução para essa questão seria um LOOP, então eu procurei um pouco mais e voltei com a function filter :

 var myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; var myValue = 80; function BiggerThan(inArray) { return inArray > myValue; } var arrBiggerElements = myArray.filter(BiggerThan); var nextElement = Math.min.apply(null, arrBiggerElements); alert(nextElement); 

Isso é tudo !

Minha resposta para uma questão semelhante é a de contabilizar os laços também e está em JavaScript simples, embora não use busca binária, então é O (N) e não O (logN):

 var searchArray= [0, 30, 60, 90]; var element= 33; function findClosest(array,elem){ var minDelta = null; var minIndex = null; for (var i = 0 ; i 

https://stackoverflow.com/a/26429528/986160

Eu gosto da abordagem do Fusion, mas há um pequeno erro nele. Assim está correto:

  function closest(array, number) { var num = 0; for (var i = array.length - 1; i >= 0; i--) { if(Math.abs(number - array[i]) < Math.abs(number - array[num])){ num = i; } } return array[num]; } 

É também um pouco mais rápido porque usa o loop for aprimorado.

No final, escrevi minha function assim:

  var getClosest = function(number, array) { var current = array[0]; var difference = Math.abs(number - current); var index = array.length; while (index--) { var newDifference = Math.abs(number - array[index]); if (newDifference < difference) { difference = newDifference; current = array[index]; } } return current; }; 

Eu testei com o console.time() e é ligeiramente mais rápido que a outra function.

Uma pesquisa binária levemente modificada na matriz funcionaria.

Para uma faixa pequena, a coisa mais simples é ter uma matriz de mapa, onde, por exemplo, a input 80 teria o valor 82, para usar seu exemplo. Para um intervalo muito maior e escasso, provavelmente o caminho a percorrer é uma pesquisa binária.

Com uma linguagem de consulta, você poderia consultar os valores à distância de cada lado do número de input e, em seguida, classificar a lista reduzida resultante. Mas o SQL não tem um bom conceito de “próximo” ou “anterior”, para lhe dar uma solução “limpa”.

Outra variante aqui é a faixa circular que liga a cabeça aos pés e aceita apenas o valor min para a input dada. Isso me ajudou a obter valores de código de caracteres para um dos algoritmos de criptografia.

 function closestNumberInCircularRange(codes, charCode) { return codes.reduce((p_code, c_code)=>{ if(((Math.abs(p_code-charCode) > Math.abs(c_code-charCode)) || p_code > charCode) && c_code < charCode){ return c_code; }else if(p_code < charCode){ return p_code; }else if(p_code > charCode && c_code > charCode){ return Math.max.apply(Math, [p_code, c_code]); } return p_code; }); } 

Aqui está o trecho de código para encontrar o elemento mais próximo de um número de uma matriz na complexidade O (nlog (n)): –

Entrada: – {1,60,0, -10,100,87,56} Elemento: – 56 Número mais próximo na matriz: – 60

Código Fonte (Java):

 package com.algo.closestnumberinarray; import java.util.TreeMap; public class Find_Closest_Number_In_Array { public static void main(String arsg[]) { int array[] = { 1, 60, 0, -10, 100, 87, 69 }; int number = 56; int num = getClosestNumber(array, number); System.out.println("Number is=" + num); } public static int getClosestNumber(int[] array, int number) { int diff[] = new int[array.length]; TreeMap keyVal = new TreeMap(); for (int i = 0; i < array.length; i++) { if (array[i] > number) { diff[i] = array[i] - number; keyVal.put(diff[i], array[i]); } else { diff[i] = number - array[i]; keyVal.put(diff[i], array[i]); } } int closestKey = keyVal.firstKey(); int closestVal = keyVal.get(closestKey); return closestVal; } }