배열의 길이를 결정하는 알고리즘

Question

은 O (log n)에서 배열의 길이를 결정할 수있는 알고리즘을 설명합니다.

Answer 1

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

Answer 2

확인. 귀하의 질문은 다소 모호하지만 제가 위에 답변 한 의견을 게시하겠습니다.

ArrayIndexOutofBounds 오류가 발생할 때까지 i = 1, 2^1, 2^2, ... 2^m을 통해 단계를 밟습니다.

그런 다음 오류가 발생한 국경을 찾을 때까지 2^(m-1)과 2^m 사이의 이진 검색을하십시오. 그건 n이야.

이 (logn) O의

편집이 제안은 당신이 당신이 ArrayIndexOutofBounds