CODEWITHSUNDEEP
arraysalgorithm
Blue_Leaf
Blue_Leaf

Reputation: 21

How to determine length of array in O(log n) time, by only calling A[i]?

I have an array of unknown length n, where each element of the array is the number 1. So its like A=[1,1,1,1.....], n times. Now I need to write an algorithm to find out the value of n.

Here is the full problem statement:

You are given an array A of length n. Each value is 1. However, you do not know what the value of n is. You are allowed to access an element i of the array by calling A[i]. If i < n, this will return 1, and if i >= n, this will return a message saying that the location does not exist (you can think of this as an error message, but it will not crash your program). Describe an O(log n) algorithm to determine the value of n.

This is what I have come up with :

Set i = 1;
while A(i-1) is true // i.e. for i <= n, it will return the element for the index (i-1)
      print i_old = i
      print i_new = 2i // doubling the value of i
      i = i_new // to run the loop again to check the array A with new value of i
else
     print no element found // when i>n

Now, this means the last index is between the last pair of i_old and i_new. So, for an array [1,1,1,1,1,1] of six elements the value of n can be between 4 and 6, i.e. it can be either 4 or 5. I am not sure about how to proceed further. What am I missing?

Upvotes: 0

Views: 1327

Answers (1)

ggorlen
ggorlen

Reputation: 56965

We can solve this using the exponential search algorithm in O(log n) time:

Assume the length is 2. Try successive powers of 2 (2, 4, 8, 16...) until an out of bounds exception is raised. This gives a guarantee of an upper bound on the possible length. Perform a right binary search between 0 and this upper bound. On each bisection iteration, if the midpoint index doesn't raise an exception, try the upper half of the search space, else try the lower half. When our bounds meet, return that index.

Python implementation:

def length(L):
    lo = 0
    hi = 1

    while 1:
        hi *= 2

        try: 
            L[hi]
        except IndexError:
            break

    while lo < hi:
        mid = (lo + hi) // 2

        try:
            L[mid]
            lo = mid + 1
        except IndexError:
            hi = mid 

    return hi

if __name__ == "__main__":
    assert all(length([1] * i) == i for i in range(1000))

Upvotes: 1

Related Questions