Ninja and Infinite Size Array — Asked in Google, Flipkart and Morgan Stanley Interview

Problem Statement :

Ninja has been given an array/list ‘ARR’ of unknown size and an element ‘TARGET.’ The ‘ARR’ is sorted in ascending order and all the elements of the ‘ARR’ are different. However, the size of the array is unknown to you. So Ninja can only access the ‘ARR’ using an interface ‘readValueAtIndex’. If you are trying to access a value from the index not present in the ‘ARR,’ you get output ’10 ^ 9 + 7’.Ninja has to find that the position of the element ‘TARGET’ if it is present in the ‘ARR’.

Sample Input:

6 7
1 3 5 7 9 11

Sample Output:

3

Approach :

Binary Search

As we know, all elements are present in ‘ARR’ are in sorted order. As we know end index ‘Ei’ of ‘ARR’ is unknown. So first, we try to find the ‘Ei’. We initialize ‘Ei’ to 1, then run a loop while ‘readValueAtIndex(Ei)’ is less than ‘TARGET, and every time we change ‘Ei’ to ‘Ei* 2’. Now, we know if the given element is present, then it is greater than ‘Ei’ / 2 and less than ‘Ei’. So we initialize ‘Si’ to ‘Ei’ / 2 and ‘Ei’ to ‘Ei’ and then apply binary search.

The steps are as follows:

Time complexity: O(log(N))
Space complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.