algorithme pour déterminer la longueur du tableau

Question

décrivent un algorithme qui peut déterminer la longueur d'un tableau dans O (log n).

Answer 1

C pseudo-style:

int lengthOfArray(p){ 
    int j = 1; 
    try{ 
     while(j < Integer.MaxValue){ 
      p[j]; // Might need to do something more with p[i] 
        // to test bound. 
      j *= 2; 
     } 
    }catch(ArrayIndexOutOfBounds e){ 
    } 
    j = searchArrayHelper(p, j/2, j); 

    try{ 
     while(1){ 
      // This loop is guaranteed to run O(log n) times or less. 
      p[j]; 
      j++; 
     } 
    }catch(ArrayIndexOutOfBounds e){ 
     j--; 
    } 

    return j; 
} 

int searchArrayHelper(p, int i, int j){ 
    try{ 
     p[j]; 
    } catch (ArrayIndexOutOfBounds e){ 
     int mid = (i + j)/2; 
     return searchArrayHelper(p, i, mid); 
    } 
    return i; 
} 

Answer 2

Ok. Je vais poster le commentaire que j'ai fait ci-dessus comme réponse, bien que votre question soit plutôt vague. Passez par i = 1, 2^1, 2^2, ... 2^m jusqu'à l'apparition de l'erreur ArrayIndexOutofBounds.

Recherchez ensuite binaire entre 2^(m-1) et 2^m jusqu'à ce que vous trouviez la frontière où l'erreur a disparu. C'est n.

Il est O (logn)

Modifier

Cette suggestion est basée sur l'extrait que vous avez posté un commentaire, où il est clair que vous êtes autorisé à détecter ArrayIndexOutOfBounds