CODEWITHSUNDEEP
algorithm
user597861
user597861

Reputation: 91

algorithm to determine the length of array

describe an algorithm that can determine the length of an array in O(log n).

Upvotes: 0

Views: 2570

Answers (2)

Olhovsky
Olhovsky

Reputation: 5559

C style pseudo code:

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

Upvotes: 1

Dr. belisarius
Dr. belisarius

Reputation: 61026

Ok. I'll post the comment I made above as an answer, although your question is rather vague.

Step through i= 1, 2^1 ,2^2, ... 2^m until the ArrayIndexOutofBounds error arises.

Then search binary between 2^(m-1) and 2^m until you find the frontier where the error is gone. That's n.

It's O(logn)

Edit

This suggestion is based on the snippet you posted as a comment, where it's clear that you are allowed to detect ArrayIndexOutofBounds

Upvotes: 3

Related Questions