алгоритм определения длины массива

Question

описать алгоритм, который может определить длину массива в O (log n).

Answer 1

Хорошо. Я отправлю комментарий, который я сделал выше, как ответ, хотя ваш вопрос довольно расплывчатый.

Шаг i = 1, 2 ^ 1, 2 ^ 2, ... 2 ^ m, пока не возникнет ошибка ArrayIndexOutofBounds .

Затем выполняйте поиск в двоичном коде между 2 ^ (m-1) и 2 ^ m, пока не найдете границу, в которой исчезла ошибка. Это п.

Это O (logn)

Редактировать

Это предложение основано на фрагменте, который вы разместили в качестве комментария, в котором ясно, что вы можете обнаружить ArrayIndexOutofBounds

Answer 2

Псевдокод в стиле C:

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;
}