Rechercher un tableau

Question

J'ai un tableau int x [] et un nombre. J'aime faire une recherche sur le tableau tel que x [i] + x [i + 1] = nombre.

Quelle est la manière la plus efficace et la plus rapide de Java?

Answer 1

Voici un pseudo code, cela devrait fonctionner. Seulement n lectures de mémoire.

buff1 = x[0] 
buff2 = 0 
for i = 1 to n - 1 
    buff2 = x[i] 
    if (buff1 + buff2) == number 
     then 
     MATCH 
    endif 
    buff1 = buff2 
endfor 

Answer 2

Si le tableau n'est pas trié et que vous effectuez seulement quelques recherches, utilisez la méthode de phoxis. On s'attend à ce qu'il s'exécute dans O (n * k), où n est la taille de x, et k est le nombre de recherches que vous ne voulez pas faire.

Si le tableau est trié, nous savons que x [i] < = nombre/2 et x [i + 1]> = nombre/2. Utilisez binary search pour trouver le (dernier) prédécesseur au nombre/2 + 1, et vérifiez si la correspondance.

int i = binaryPredecessor(x , number/2 + 1); 
if(x[i] + x[i+1] == number){ 
    return i; 
} 
else if(x[i-1] + x[i] == number){ 
    //The case where x[i] == number/2, and we found the last of two occurrences 
    return i-1; 
} else { 
    //No match exists 
    return -1; 
} 

L'exécution est O (log (n) * k).

Si vous faites beaucoup de recherches, il peut être utile de trier la matrice et d'utiliser la méthode ci-dessus. Le tableau peut être trié dans O (n * log (n)) [voir mergersort]. Donc, si vous voulez faire plus de recherches de log (n), ça vaut le coup de trier le tableau. (Si k est proche de log (n), faites des tests, pour voir ce qu'il y a de mieux :))