# Programming Interview Questions 17: Search Unknown Length Array

Given a sorted array of unknown length and a number to search for, return the index of the number in the array. Accessing an element out of bounds throws exception. If the number occurs multiple times, return the index of any occurrence. If it isn’t present, return -1.

The straightforward solution is to scan the array linearly until we find the number, or go out of bounds and get an exception. In the former case we return the index, the latter case returns -1. The complexity is O(N) where N is the number of elements in the array that we don’t know in advance. However, in this approach we are not taking advantage of the array being sorted. So we can use some sort of binary search to benefit from sorted order.

Standard binary search wouldn’t work because we don’t know the size of the array to provide an upper limit index. So, we perform one-sided binary search for both the size of the array and the element itself simultaneously. Let’s say we’re searching for the value k. We check array indexes 0, 1, 2, 4, 8, 16, …, 2^N in a loop until either we get an exception or we see an element larger than k. If the value is less than k we continue, or if we luckily find the actual value k then we return the index.

If at index 2^m we see an element larger than k, it means the value k (if it exists) must be between indexes 2^(m-1)+1 and 2^m-1 (inclusive), since the array is sorted. The same is true if we get an exception, because we know that the number at index 2^(m-1) is less than k, and we didn’t get an exception accessing that index. Getting an exception at index 2^m means the size of the array is somewhere between 2^(m-1) and 2^m-1. In both cases we break out of the loop and start another modified binary search, this time between indexes 2^(m-1)+1 and 2^m-1. If we previously got exception at index 2^m, we may get more exceptions during this binary search so we should handle this case by assigning the new high index to that location. The code will clarify everything:

```def getIndex(arr, num): #check array indexes 0, 2^0, 2^1, 2^2, ... index, exp = 0, 0 while True: try: if arr[index]==num: return index elif arr[index]<num: index=2**exp exp+=1 else: break except IndexError: break   #Binary Search left=(index/2)+1 right=index-1 while left<=right: try: mid=left+(right-left)/2 if arr[mid]==num: return mid elif arr[mid]<num: left=mid+1 else: right=mid-1 except IndexError: right=mid-1   return -1```

The complexity of this approach is O(logN) because we use binary search all the time, we never perform a linear scan. So it’s optimal. Binary search is one of the most important algorithms and this question demonstrates an interesting use of it.

VN:F [1.9.22_1171]
Rating: 9.3/10 (46 votes cast)
Programming Interview Questions 17: Search Unknown Length Array, 9.3 out of 10 based on 46 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• kishore

when you case by case, does this need recursive solution inn case of large data set?
If array size is million then we have to do multiple binary search attempts to get an index.

• sreeram

can u pls tell me why only power of 2 and why not power of 3

• Sumeet Kataria

If an array is of size say 13(unknown for user), and the element to be searched is at 12th position in the array.
Your algo will see that element is greater than 2^3 indexed element. Then you will look for 2^4 = 16th index which is greater than array size, results in error. But searching element resides there.

How will you find that??

• jarora

Will sizeof(arr)/sizeof(arr[0]) no work here?

• jarora

*not

• AB

That’s exactly the problem. In C++ you can send a pointer to data as an argument and it won’t work here

• Dinesh

Could you explain how O(logN) time complexity was derived for this solution? thanks in advance.

• Sai Talasila

Nice solution. Small suggestion. Correct me if I am wrong. In case of out of bounds exception, can we use recursions to do the modified binary search from the location, 2^(m-1). This would avoid trying to handle the out of bounds exception repeatedly

• Gyoho

Brilliant idea! Never thought another way of binary search. This way can definitely achieve O(logN) and it’s very useful in case of streaming data. Thanks for sharing!!